acceptodds
Under review as a conference paper at ICLR 2027

Base-Rate Dilution: A Zero-Cost Attack That ROC-AUC Cannot See

Abstract

Graph anomaly detectors are predominantly evaluated with class-conditional ranking metrics such as ROC-AUC. We identify a threat model these metrics are structurally blind to. An adversary that never touches its own malicious activity can degrade a deployed detector by generating additional genuinely benign events, lowering the base rate of the anomalous class. This base-rate dilution carries no perturbation budget, produces no detectable artifact, and preserves attack functionality exactly; it is therefore outside the scope of existing robustness defenses, which assume the attacker perturbs an input. We give an elementary but consequential characterization: precision decays as Θ(1/m) in the injected volume for any detector with nonzero benign false-positive rate, and is asymptotically invariant if and only if the detector's flagged set is null under the benign generating distribution. We show that ranking-metric invariance requires a separate property score locality under benign augmentation which message-passing architectures do not satisfy, and that the two properties have been conflated. Building on this, we propose feasibility-gated detection: a learned scorer composed with a non-learned hard mask derived from deterministic feasibility constraints, so that the benign-null support property holds architecturally for arbitrary parameter values rather than being encouraged by training. The gate bounds recall by construction; the learned component's role is to separate benign from adversarial constraint violations within the infeasible set, a distinction no fixed rule expresses. We evaluate on DARPA TC E3 provenance graphs against ungated and feature-augmented baselines, measure an empirical dilution exponent with confidence intervals, characterize the recall/robustness frontier, and test an adaptive attacker restricted to the feasible set. We also use the dilution exponent as a diagnostic for benign-noise realism in existing benchmarks, and report results on a second graph anomaly domain to assess generality. Building on Axelsson's base-rate analysis of intrusion detection, we argue that ranking metrics should be reported alongside a dilution-robustness measurement.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
graph anomaly detection, adversarial robustness, base-rate shift, evaluation metrics, constraint-gated neural architectures

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_y11ROpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper investigates the reliability of graph anomaly detection in scenarios where class base rates are actively manipulated by an adversary, and introduces the "base-rate dilution" threat model. The authors propose a "feasibility-gated detection" approach, which employs hard structural constraints—independent of model parameters—to restrict the detection model so that it only issues alerts for edges that violate specific system invariants. This architectural design ensures a zero false-positive rate on benign data.

Critical strengths
  1. The distinction between the threat model and classical perturbation-based attacks is clearly drawn.
  2. The "critical control" design is well-conceived.
Critical weaknesses
  1. The distinction between the core phenomenon presented and the classic "base-rate fallacy" is not sufficiently sharp.
  2. The term "Zero-Cost Attack" is an overstatement.
  3. The HARD rules were selected from 15 candidates based on their violation rate on benign data. It should be explicitly clarified whether the HARD/SOFT classification was determined solely using benign data from the training/validation sets.
  4. The coverage of malicious edges by the proposed defense is very low; the 11 HARD rules discussed cover, on average, only about 10.7% of such edges.
  5. The scope of the learning models examined is quite narrow, with the core experiments focusing almost exclusively on GraphSAGE.
  6. The cross-scenario experiments actually expose a fundamental vulnerability in the defense: a violation rate of benign invariants as low as 0.00009% is sufficient to cause the precision to decline again as a function of mm.
  7. There is a lack of comparison with more direct, operational defenses.
  8. I will adjust my score based on the authors' rebuttal.
Questions for authors

Q1. What is the core technical innovation of "base-rate dilution" compared to the classic "base-rate fallacy"?

Q2. Does the attack remain effective if the attacker has a realistic resource budget?

Q3. Why is there no comparison between dynamic thresholds and "alert-budget" defense?

Q4. What is the actual recall ceiling for "HARD rules"?

Q5. How are "benign-null" cases verified and maintained during deployment?

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

A graph anomaly detector is usually judged by a ranking metric computed at a fixed class ratio. This paper points out that an adversary can change that ratio by generating additional, entirely genuine benign activity, without touching the malicious events at all. Any nonzero benign false-positive rate then drives precision toward zero as the injected volume grows, while the ranking metric can remain flat. The authors characterise when precision survives, propose a detector that multiplies a learned scorer by a non-learned mask derived from structural invariants that never fire on benign traffic, and evaluate on system-provenance graphs with a second domain used to reproduce the phenomenon.

Critical strengths

The critical control is the best thing in this paper and it teaches a lesson that generalises well beyond the specific setting. Giving the GraphSAGE encoder the same invariant-violation indicators as ordinary input features, and showing that its precision then collapses in a manner visually indistinguishable from the fully ungated baseline, demonstrates something that is easy to assert and rarely shown: supplying a network the information it would need to be benign-null does not make it benign-null, because nothing in the training objective forces the false-positive rate to be exactly zero rather than merely small. Including this as a designed control rather than as an afterthought is exactly right, and it is what justifies the architectural choice the paper makes.

The noise-realism audit is a second strength and an unusually honest one. The authors show that their own earlier mimicry-style noise generator manufactures invariant violations at rates high enough to masquerade as detector weakness, then replace it with a subgraph resampler that achieves a zero violation gap across every rule the gate depends on. Papers rarely audit their own stress test and almost never report that an earlier version of it was invalid. The same care shows up in the cross-scenario analysis, where every one of the residual false positives is traced to a genuine invariant violation in the injected traffic rather than attributed vaguely to distribution shift. This is the kind of self-scrutiny that makes the empirical claims easy to trust.

Critical weaknesses

The paper claims four contributions, and two of them do not carry the weight the framing assigns them, which I think sells the real result short. Proposition 1 is three lines of algebra on a closed form that the paper itself writes down immediately beforehand, and its content is close to Axelsson's observation, which the paper cites. Presenting it as a tight characterisation and a headline contribution invites a reader to measure the paper against a theoretical standard it is not trying to meet. The genuine contribution is empirical: the dissociation between ranking stability and precision collapse, the control experiment, and the dilution exponent as a reportable diagnostic. I would encourage restructuring so that the control experiment leads and Proposition 1 appears as the motivating observation it is. Nothing needs to be removed, and the paper reads as stronger rather than weaker for it.

The second concern is that the proposed defense is narrower than its presentation suggests, by the paper's own measurements. Recall is capped at roughly a tenth of malicious edges, against forty-four percent for the ungated baseline before dilution, and the adaptive-adversary appendix reports that four of seven attack objectives are achieved in every trial without violating a HARD invariant, receiving a gate score of exactly zero. So against a competent adversary pursuing those objectives, the gate detects nothing, and against an adversary not diluting at all, an operator gives up most of their recall. The limitations section states both facts plainly, which I credit, but the paper still frames feasibility-gated detection as a contribution on its own terms. The honest and I think more useful framing is as a dilution-robust component in a layered system, and the paper is one experiment away from demonstrating that: run the gate and the ungated detector together with separate alert queues, and report the combined operating characteristics under dilution. That would show an operator what they actually get, rather than asking them to choose between two unattractive single detectors. Relatedly, the defense is evaluated on one provenance dataset only — the second domain reproduces the phenomenon but not the gate, for reasons the paper explains honestly — so some acknowledgement that the HARD set is tied to one schema would be appropriate in the main text.

Questions for authors

The question most likely to change my view is about composition. Have you measured what a layered deployment looks like — gate and ungated detector run together, alerts kept in separate queues — under the same dilution sweep? If the gated queue stays at precision one while the ungated queue degrades predictably, an operator can triage accordingly, and that seems to me the deployable form of this idea.

I have two clarifications. In Table 2, the rule-only configuration using all fifteen rules is reported with an exponent of zero but an R² of zero as well, whereas the other flat configurations report R² of one. Could you explain what the fit is doing there? And on threshold policy: thresholds are calibrated once at zero injected volume and frozen, which I agree is the right choice for measuring stability. Is there a realistic operational regime in which a defender would recalibrate, and if so does the gate retain any advantage once both detectors are allowed to move their operating point?

Reviewer_pw6yOpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

This paper studies the robustness of graph anomaly detectors when an adversary injects benign activity without modifying the malicious events (“base-rate dilution”). Specifically, the authors argue that ROC-AUC can stay stable under such injection while precision collapses. To address this, they show that precision decays unless the detector has zero false positives on benign data, and propose feasibility-gated detection, which combines a GraphSAGE scorer with a fixed mask built from structural rules that benign data never violates. Experiments on DARPA TC E3 and Elliptic show that ungated detectors suffer precision collapse, while the gated detector keeps precision at 1.0 within a single scenario.

Critical strengths
  1. The problem is practically relevant. It points out a real blind spot in how graph anomaly detectors are evaluated: ROC-AUC alone can hide precision collapse when the benign population grows.
  2. The idea is simple and easy to understand.
Critical weaknesses
  1. The writing is far below the ICLR standard.
  • The abstract is split into two long paragraphs that mostly list experiments.
  • Key content is moved to the appendix: Section 7.4 is only three sentences, and the adaptive-adversary study claimed as a contribution appears only in Appendix A.4.
  • The main metric, the dilution exponent α̂, is never formally defined.
  • Figures are poorly prepared: the Figure 1 title is truncated, and Figure 2 uses raw code names such as “Dir1_1r3_to_5m6r”.
  • There are duplicated sentences (Section 7.3) and wrong cross-references (Limitations cites Section 7.3 for the second domain).
  • Numbers are inconsistent between text and tables (~90% in Section 5 vs. 77.37% in Table 1).
  • The tone is informal in places (e.g., “lottery ticket for a false alarm”).
  1. The motivation and contribution are unclear. The theory is a known result: Proposition 1 is, as the authors admit, elementary, and the dependence of precision on class prevalence is the well-known base-rate fallacy (Axelsson, 2000; Saito & Rehmsmeier, 2015). The threat model is also not new. Mimicry attacks against provenance-based IDS (Goyal et al., NDSS 2023) already evade detection by adding benign behavior without modifying the attack, and graph injection attacks (e.g., TDGIA, KDD 2021) inject new nodes without modifying existing edges, yet neither is cited. As a result, it is unclear what new problem this paper studies and what its contribution is beyond restating known results.
  2. The proposed defense is essentially a rule engine with very low recall. The gated GraphSAGE performs identically to the HARD rule-only detector on every metric (Table 3), so the learned component contributes nothing. It catches only 10.7% of malicious edges, compared with 44% for the ungated baseline (Section 7.1), and it fails to detect any of the attacks of an adaptive attacker that avoids the rules (Appendix A.4).
Questions for authors

Please see my weaknesses to polish and rewrite this paper.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.