- Rating
- 2
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
This paper studies the adversarial robustness of graph anomaly detection (GAD) models along two lines: whether anomalous targets can escape detection, and how much an attacker has to pay, in graph modifications, to make that happen. The authors propose a cost-aware robustness evaluation framework. They first calibrate a detector-independent cost metric, GMC, on normal data, using reference-event normalization so that attribute modifications, edge additions, and edge deletions are measured on a common scale. They then test whether anomaly nodes that were previously detected still evade detection after test-time perturbations.
The experiments span ten GAD detectors and six datasets, with adversarial attacks run on five datasets across 83 detector–attack combinations in total. Perturbations come in three forms—structural, feature-based, and hybrid—and results are reported uniformly in terms of attack success rate (ASR), AUC change, and modification cost.
Three findings stand out. Robustness varies considerably across perturbation channels. Successful target evasion does not necessarily come with a drop in overall AUC. And attack effectiveness is not simply or directly tied to modification cost. The paper further analyzes shifts in anomaly scores and detection thresholds, and discusses design principles for cost-aware robust GAD.
Critical strengths
- Meaningful evaluation of target-level evasion beyond conventional detection metrics.
The paper highlights an important limitation of evaluating adversarial robustness solely through global AUC degradation. By separating target escape from overall ranking performance, the proposed evaluation gives a more informative picture of adversarial effectiveness in GAD. This distinction is backed by concrete results. For example, Table 18 shows that FGA achieves an ASR of 0.540 (34/63) against LightGAD on YelpChi-5K, while overall AUC slightly improves (ΔAUC = −0.021). This illustrates that substantial target-level evasion can occur without a corresponding decrease in global AUC. I consider this a valuable empirical observation that motivates the proposed evaluation framework.
- Broad empirical investigation with useful cross-detector comparisons.
The study examines different GAD mechanisms under structural, feature-based, and hybrid perturbations, offering useful insight into their heterogeneous responses. For example, under the same NFF perturbation on Weibo, LightGAD reaches an ASR of 0.737, whereas SAGAD reaches only 0.073 (Table 19). Such comparisons show that identical graph modifications can have substantially different effects on different detectors. The paper also provides detailed attack configurations, per-condition results, and additional analyses in the appendix, which improves the transparency of the evaluation. These findings offer useful empirical evidence for understanding the robustness of existing GAD methods.
Critical weaknesses
- Insufficient validation of the proposed Graph Modification Cost (GMC) metric and its relationship to successful evasion.
GMC is a central contribution of the paper, but its validity as a measure for comparing modification burden across perturbation channels still needs further validation. The metric combines attribute changes, edge additions, and edge deletions via reference-event normalization and equal-weight aggregation. However, the choice of reference events and the resulting cross-channel cost equivalence depend on modeling choices that have not been sufficiently examined. Appendix B.1 shows bootstrap stability under the chosen calibration scheme, but this does not establish whether the main conclusions hold under alternative reference scales, channel weights, or simpler modification-cost measures.
More importantly, Section 4.4 computes ASR over previously detected targets, but summarizes GMC over all modified targets, including those that do not escape. The paper acknowledges this distinction, but the coexistence of successful evasion and low median GMC does not necessarily establish that successful evasion was achieved at low overall modification cost. This limits the interpretation of the joint effectiveness–cost results, which are central to the paper's claims. A more directly paired analysis linking modification costs to escape outcomes, together with sensitivity experiments, is needed to substantiate this central claim.
- Limited comparability and statistical reliability of the adversarial evaluation.
The evaluated attacks operate under substantially different budgets and information privileges. For example, Greedy uses a global budget of 10 actions shared across all targets, while Nettack-GAD allows 10 actions per target . Because of this, it is difficult to determine whether the observed differences in attack effectiveness arise from detector robustness, perturbation channels, or differences in attack strength and coverage. Comparisons under identical non-adaptive perturbations remain informative, but cross-attack conclusions would benefit from controlled budgets or modification costs.
In addition, the adversarial evaluations rely on a single random seed, and several combinations were not evaluated due to computational cost. Appendix A.5 also documents that some effectiveness and GMC measurements come from separate attack executions or replays, with small differences in the final perturbations for certain conditions, including YelpChi-5K. While the authors transparently report these limitations, they still weaken confidence in the joint effectiveness–cost comparisons. Budget-controlled comparisons, repeated evaluations for representative conditions, and strictly matched effectiveness–cost measurements would substantially strengthen the experimental conclusions.
Questions for authors
Q1. Relationship between modification cost and successful evasion
ASR is computed over previously detected targets, but GMC is summarized over all modified targets, including those that remain detected. Right now, showing that some attacks have both nonzero ASR and low median GMC doesn't prove that the successful evasions themselves were cheap. Could the authors provide a directly paired analysis of modification cost and escape outcomes, perhaps separating directly modified targets from indirectly affected ones?
Q2. Validity and sensitivity of GMC
The cross-channel comparability of GMC depends heavily on the chosen reference events and equal-weight normalization. Appendix B.1 shows calibration stability under bootstrap resampling, but that doesn't tell us whether the cost rankings hold under different normalization choices. How sensitive are the main cost rankings and low-cost conclusions to the reference-event definitions, channel weights, and numerical floors? And what does GMC actually give us beyond simpler metrics like raw modification counts or normalized attribute changes?
Q3. Comparability and reproducibility of attack evaluations
The attacks operate under very different budgets—Greedy has a global budget of 10 actions, while Nettack-GAD gets 10 actions per target. How much of the observed difference in attack effectiveness comes from these budget/coverage differences rather than detector robustness? A budget-controlled comparison or repeated runs on a few representative conditions would help. Also, when effectiveness and cost come from different perturbation replays, can you verify that they match on the exact same final attacked graphs?
Q4. Influence of threshold recalibration on target escape
The evaluation recomputes the detection threshold after modification using the same normal reference nodes, so target escape can come from score changes, threshold shifts, or both. The decision-margin diagnostics are helpful, but could the authors quantify how the main ASR conclusions change if they use the original clean-graph threshold instead of the recalibrated one? That would clarify how much of the evasion is driven by target-score changes versus decision-boundary shifts.