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

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.