acceptodds
Under review as a conference paper at ICLR 2027

How Robust Are Graph Anomaly Detectors, and At What Cost?

Abstract

Graph anomaly detection (GAD) aims to identify rare or suspicious entities from their attributes and relational patterns, with applications in fraud detection, risk control, and network security. Existing evaluations, however, largely focus on detection performance on clean graphs, overlooking that anomalous actors may strategically modify these attributes or relations to evade detection. This raises two fundamental questions: how robust are different GAD mechanisms to such modifications, and how much modification is required for successful evasion? We introduce a cost-aware robustness evaluation framework that jointly characterises target escape and graph modification cost. To quantify modification burden across perturbation channels, we develop a detector-independent, normality-calibrated cost that places attribute changes, edge additions, and edge deletions on a common reference scale. Across diverse GAD mechanisms, attacks, and graphs, we find that robustness is strongly channel-dependent, target escape can diverge substantially from global ranking degradation, and attack effectiveness does not reliably reflect modification cost. We further connect these findings through the relationship among graph modification, anomaly evidence, and decision margin, providing a unified view of how modifications lead to successful evasion. This analysis motivates a design principle for economically robust GADs: under a false-positive constraint, detection should rely on evidence that cannot be readily neutralised by low-cost modifications, with multi-channel complementarity providing one potential route toward this goal.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
Graph Anomaly Detection, Adversarial Robustness, Adversarial 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_89hWOpenReview ↗
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
  1. 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.

  1. 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
  1. 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.

  1. 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.

Reviewer_NCLaOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies the adversarial robustness of graph anomaly detectors, focusing on both target evasion and the cost of graph modifications. The authors propose a two-dimensional evaluation framework that measures attack success rate (ASR) and global AUC degradation, and introduce Graph Modification Cost (GMC) to quantify attribute changes, edge additions, and edge deletions relative to normal patterns in the clean graph. They evaluate ten GAD detectors on six datasets and conduct attack experiments using five attacks across five datasets. The results show that robustness varies substantially across attack types, successful target evasion does not necessarily lead to global performance degradation, and attack effectiveness does not consistently reflect modification cost. The authors further analyze hyperparameter sensitivity and decision-margin changes to investigate detector vulnerabilities and discuss implications for robust GAD design.

Critical strengths

1.The paper distinguishes targeted evasion from global detection performance by evaluating attack success rate (ASR) and area under the ROC curve (AUC), providing a more comprehensive assessment of graph anomaly detection (GAD) robustness.

2.The proposed Graph Modification Cost (GMC) metric enables cost-aware comparisons of attribute and structural modifications. Experiments across multiple detectors, datasets, and attacks show that attack effectiveness does not necessarily correspond to modification cost.

Critical weaknesses
  1. The proposed GMC is largely heuristic, with limited theoretical analysis of how graph modifications affect attack success rate (ASR) and AUC degradation. The authors should further analyze the relationship between modification cost, anomaly scores, and evasion effectiveness.

  2. GMC quantifies the cost of existing attacks but does not investigate the minimum cost required for successful evasion. The authors should formulate a cost-minimization objective under an evasion constraint or evaluate attack success under different GMC budgets.

  3. The evaluation includes synthetic and injected anomalies, which may not fully reflect real-world scenarios. Experiments on more datasets with naturally occurring anomalies would strengthen the practical validity of the findings.

  4. Table 1 has poor readability and inconsistent baseline coverage. For example, only three detectors are reported on Gen-1000 and two on YelpChi-5K. The authors should clarify missing results and improve the presentation of experimental comparisons.

Questions for authors

See Weaknesses.

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

This paper investigates the adversarial robustness of graph anomaly detection (GAD) methods from two perspectives: target escape and graph modification cost. It introduces a cost-aware evaluation framework that measures whether previously detected anomalies evade detection after perturbation and quantifies the modification burden through a detector-independent Graph Modification Cost (GMC). The proposed cost metric normalizes attribute changes, edge additions, and edge deletions onto a common scale. Experiments across multiple GAD methods, datasets, and attack strategies reveal substantial differences in robustness across perturbation channels and highlight the discrepancy between target-level evasion and global detection performance. The paper further analyzes decision-margin changes and discusses implications for developing economically robust GAD methods.

Critical strengths
  1. Meaningful evaluation perspective. The paper investigates an important yet insufficiently explored aspect of GAD robustness by considering not only whether anomalous nodes can evade detection, but also the modification burden associated with such evasion.

  2. Relatively comprehensive empirical analysis. The evaluation covers diverse GAD mechanisms, datasets, and perturbation strategies. The distinction between target-level escape and global AUC degradation provides useful insights into the limitations of conventional robustness evaluation.

Critical weaknesses
  1. Insufficient justification of anomaly-preserving adversarial evasion. The paper assumes that anomalous nodes remain anomalous after their attributes or connections are modified. However, this assumption is not sufficiently justified, particularly for synthetic or injected anomalies whose labels are directly associated with abnormal attributes or structural patterns. For example, the NFF attack moves target features toward neighborhood averages, potentially removing the very evidence that originally defines the anomaly. In such cases, successful evasion may reflect the elimination of anomalous characteristics rather than a genuine failure of detector robustness. The paper should clarify which perturbations preserve the underlying anomaly semantics and how this distinction affects the interpretation of ASR.

  2. Questionable validity of the proposed cross-channel modification cost. GMC is a central contribution, but its ability to provide meaningful comparisons across attribute changes, edge additions, and edge deletions remains insufficiently justified. The proposed formulation relies on statistical feature variability, edge plausibility, and reference-event normalization, which do not necessarily correspond to the actual difficulty or feasibility of modifications. Moreover, the equal-weight combination of normalized costs assumes cross-channel comparability without sufficient validation. Consequently, the reported relationships between attack effectiveness and modification burden may depend substantially on the chosen cost formulation, weakening the practical interpretation of the proposed cost-aware robustness framework.

  3. Limited evidence for the cost required to achieve successful evasion. Although the paper aims to investigate how much modification is required for successful evasion, its experiments primarily measure GMC after applying attacks with predefined and heterogeneous perturbation strategies. These attacks differ in their budgets, information access, and optimization objectives, and none explicitly minimizes GMC subject to successful evasion. Therefore, the observed costs reflect the behavior of particular attack implementations rather than the minimum modification burden needed to compromise a detector. Without cost-constrained attacks or comparable ASR–cost trade-off curves, it is difficult to determine whether a detector is genuinely resistant to low-cost evasion or whether the evaluated attacks are simply inefficient.

Questions for authors
  1. How do the authors ensure that the perturbations preserve the underlying anomaly semantics, particularly for synthetic and injected anomalies?

  2. How sensitive are the GMC-based conclusions to the reference-event definitions, normalization choices, and equal weighting of different perturbation channels?

  3. Can the authors provide cost-constrained evaluations or ASR–GMC trade-off curves to better establish the modification burden required for successful evasion?

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.