acceptodds
Under review as a conference paper at ICLR 2027

Beat the Counter First: A Baseline for Temporal-Graph Anomaly Models

Abstract

Progress in streaming, edge-level graph anomaly detection (GAD) has been marked by increasingly elaborate architectures, from count-min-sketch chi-square tests to memory-augmented attention networks. Yet the empirical gains attributable to this added complexity have not been systematically evaluated. We propose SimpleCount, a reference with no learning- or gradient-descent-based parameter fitting that selects one scalar feature per dataset from a fixed pool of counts, recencies, first-occurrence indicators, and count-derived transforms. We compare SimpleCount with two temporal-graph detector models and an IsoForest control fitted to the complete feature vector across five public datasets and one synthetic dataset. SimpleCount matches or exceeds SLADE - a state-of-the-art GAD method - on three of six datasets and exceeds IsoForest on all six. We report paired statistical tests and five-seed SLADE evaluations. SLADE requires 23 to 133 more wall-clock time than SimpleCount. On synthetic datasets, pre-event structural scores recover the planted signal at AUC up to , while all evaluated GAD models remain near random. SimpleCount is not a replacement GAD model, rather, its purpose is to highlight that the benefit of complexity is dataset-dependent, and every claimed gain should be reported against a strong one-feature reference together with its compute cost.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
Temporal graph anomaly detection, count-based baselines, graph representation learning, empirical benchmarking, computational efficiency.

Reviews

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

The paper examines whether complex temporal graph anomaly detectors provide enough benefit over simple features. It introduces SimpleCount, which uses training labels to select one of 14 historical features. Across five public datasets and one synthetic benchmark, it compares detection performance and runtime against SLADE, MIDAS-F, and Isolation Forest. The results suggest that simple features can be competitive on some datasets at substantially lower runtime.

Critical strengths
  • The paper addresses a useful evaluation question. Comparing complex models against a strong simple baseline helps assess whether their additional complexity produces meaningful gains. This is practically relevant for streaming anomaly detection.

  • The proposed baseline is simple and interpretable. Each score comes from a single count, recency, or first-occurrence feature. This makes it easy to understand which basic signals are predictive in each dataset.

  • The evaluation considers both performance and computational cost. Runtime measurements make the trade-offs clearer. Five-seed SLADE results, per-feature analysis, and supplementary AUPRC results also provide useful context beyond the main ROC-AUC comparison.

Critical weaknesses
  • A single Isolation Forest result is not enough to assess whether combining features helps. The experiment shows that the tested Isolation Forest configuration does not outperform the selected single feature. Other simple models, such as a shallow decision tree, may capture useful interactions between features. Moreover, SimpleCount uses labels for feature selection, while Isolation Forest does not. A lightweight multi-feature baseline using the same training labels would make this comparison more informative.

  • The experimental coverage could be narrow, and the relation to existing benchmarks needs clarification. The main experiments include only one neural anomaly detector, SLADE, while GraphMixer is evaluated on only two datasets. This limits how broadly the findings on the benefits of model complexity can be generalized. The paper should also discuss and evaluate on BAG [a], which evaluates 25 models on 10 datasets covering dynamic edge- and node-level anomaly detection, and clarify what additional insights this study provides.

[a] Hua, F., Qi, Y., Wei, Z., Tian, Y., Xu, C., Wu, X., Li, J. and Guo, J., 2026, March. Bag: Benchmarking anomaly detection on dynamic graphs. In Proceedings of the AAAI Conference on Artificial Intelligence (Vol. 40, No. 17, pp. 14892-14900).

Questions for authors

N/A

3 comments

We thank the reviewer for the suggestions and the pointer to BAG. All changes are highlighted in blue in the revised PDF.

W1: We agree, and have added exactly this comparison (Appendix H, summarised in Section 5.1, highlighted in blue). Logistic regression, histogram gradient boosting, and an MLP are fitted to the same 14 features using training labels, with configurations selected on validation AUROC. These are multi-feature baselines that use the same labels as SimpleCount, and boosting can capture interactions between features. They recover additional signal on some datasets. The unsupervised IsoForest remains in the main text as the label-free control, and the label-usage table (Section 4.3) states how each method uses labels. For example, on Bitcoin-Alpha logistic regression raises AP from 11.06% for the single feature to 19.01%, above DyGFormer’s 15.83% (Table A4).

W2: We have broadened the evaluation (Appendix H, summarised in Section 5.1, highlighted in blue). GraphMixer, DyGFormer, TGN, and CAWN are now evaluated on all five interaction datasets, alongside SLADE, and DyGFormer also on Theia and TRACE. The extended evaluation also adds Theia, TRACE, MIDAS DARPA, Synth-Quad, and two email streams. Across 27 comparisons with neural methods, the single feature matches or exceeds neural AUROC in 20, while neural models lead on the Bitcoin graphs and the email streams.

We have also added BAG to Related Work (highlighted in blue). All five public datasets we use are among BAG’s ten, although BAG evaluates injected rather than organic anomalies on Bitcoin-Alpha and Bitcoin-OTC. Our study adds what BAG does not cover:

  • a one-feature activity reference and a count-based streaming detector, neither of which BAG includes
  • paired significance tests for each comparison
  • end-to-end compute cost on every dataset in the main comparison, where BAG reports compute on one dataset
  • planted-structure probes with a label-free check that the planted signal is recoverable
  • the finding that a single selected statistic matches or exceeds neural AUROC in 20 of 27 comparisons.

I would like to thank the authors for their detailed response. The rebuttal has addressed my concerns.

Thank you for taking the time to review and read the rebuttal!

Reviewer_VMgkOpenReview ↗
Rating
2(+1)
Confidence
2
Informativeness
2(+1)
Presentation
2(+1)
Soundness
2
Read review
Paper summary

The paper argues that temporal graph anomaly detection models should be evaluated against a strong, simple baseline before their added complexity is credited. To this end, the authors propose SimpleCount, which selects a single count, recency, or first-occurrence feature per dataset from a fixed pool of 14 features using the training split. SimpleCount is compared against SLADE (a state-of-the-art temporal-graph detector), MIDAS-F, and an IsoForest model fit to all 14 features across five public datasets and one synthetic dataset. The authors report that SimpleCount matches or exceeds SLADE on three of six datasets at 23-133x less wall-clock time, and that the benefit of model complexity is dataset-dependent.

Critical strengths
  • The intention of the paper is apparent and relevant, as increasing model complexity also increases evaluation time, often for marginal gains. Reporting gains against a strong simple baseline together with compute cost is a reasonable evaluation practice.
Critical weaknesses
  • The writing style in the introduction feels disjointed and the motivation is unclear. The second paragraph feels as if it belongs in a related work section. Instead, that paragraph should be used to connect the ideas of paragraph one to the motivation for creating a new method for comparison.
  • The related work section lists methods in the field (lines 091-095) rather than discussing what each method contributes to the area and how it relates to this work.
  • Notation should be defined when it is first introduced. For example, (u,v,t) on line 149 and b_k on line 155 are used before being clearly defined. Algorithm 1 also introduces several symbols (C_x, C^(b)_x, T_x, M, S, m, C-bar) that are never explained in the text.
  • The methodology section is unclear in what it is proposing. Section 3.1 does not define "recency" or most of its notation, and reads more as an experimental setup than a method. The final paragraph of Section 3.1 lacks discussion and motivation for why the selection procedure is computed the way it is. Section 3.2 provides no intuition for why DeLong correlated-ROC tests are used.
  • Algorithm 1 is never referenced in the text.
  • SimpleCount is never explicitly defined in the methodology. Section 3.1 describes the feature pipeline, but the method itself is only named in the introduction and in Section 4.3.

Minor Comments/Typos

  • This sentence feels out of place as the reader has not been introduced to the setting or the features yet: "In our setting, the EdgeBank-∞\infty rule enters as the is_new_pair feature."
  • Lines 134-137 would fit better in the introduction and motivation rather than in related work.
  • In Section 3.3, clarify that Synth-Triangle is a synthetic dataset introduced by the authors.
  • Table 1 caption should state what |E| means.
  • The paper uses "streaming-graph anomaly detection," "temporal edge-level anomaly detection," and "dynamic graph anomaly detection" interchangeably. One term should be chosen and defined, particularly since the evaluation protocol (a chronological train/test split with offline training) is not a streaming setting.
  • In-text citations are missing parentheses throughout (e.g., "MIDAS-F Bhatia et al. (2022)"), and the reference list is not in alphabetical order.
Questions for authors
  1. Could the authors provide a self-contained definition of SimpleCount, including how “recency” is computed and how the selected feature produces an anomaly score? How does Algorithm 1 implement this procedure?
  2. What motivates the feature-selection procedure in Section 3.1? What criterion determines the selected feature, and what information from the training split does this selection require?
3 comments

We thank you for the detailed comments on the presentation. We have addressed each point below and have uploaded a revised PDF with all changes highlighted in blue.

W1: We have rewritten the first two paragraphs of the introduction (highlighted in blue). The first now defines the task. The second, which previously summarised related work, now explains why a new reference is needed with a detailed discussion in Section 2.

W2: We have rewritten that paragraph (Section 2, “Temporal edge-level anomaly detection” highlighted in blue). It now states what each method contributes and how it relates to our work. MIDAS-F keeps count-min sketches and tests for bursts, SedAnSpot uses random-walk proximity in a sampled graph, and F-FADE models how often each node pair interacts over time. SimpleCount keeps simple count statistics but drops the machinery built around them.

W3: We have addressed this (highlighted in blue). The notation (u,v,t) is now defined where it first appears, in the first paragraph of the introduction. Section 3.1 defines b_k and explains every symbol used in Algorithm 1, and the algorithm caption now points there.

W4: We have revised Section 3 (highlighted in blue).

  • Section 3.1 now defines recency as Δx=tk−Tx[qx]\Delta_x = t_k − T_x[q_x], the time since a key last appeared. It now defines SimpleCount explicitly (see W6) and explains the selection rule. We select from a pool because the most informative statistic differs across datasets. We select on AUROC because it needs no threshold and is invariant to monotone transforms, so features on different scales need no calibration.

  • Section 3.2 now gives the intuition for the DeLong test. All methods score the same test edges, so their AUROC estimates are correlated, and treating them as independent misstates the uncertainty of their difference. DeLong’s test estimates that uncertainty from each test edge’s contribution to both AUROCs.

W5: Section 3.1 now refers to Algorithm 1 where it introduces the feature pass (highlighted in blue).

W6: Section 3.1 now contains an explicit SimpleCount paragraph (highlighted in blue). It states the selection criterion and the resulting score, sk=σ∗⋅ϕk(j∗)s_k = \sigma^{*}\cdot\phi_k^{(j^*)}

Minor comments: Thank you for the detailed list. All of these have been addressed and highlighted in blue throughout the updated paper to make it easier to read and follow.

Q1: Section 3.1 now gives a self-contained definition (highlighted in blue). Algorithm 1 makes one chronological pass over the edges. For each key of edge k (its pair, source, and destination), it maintains a lifetime count, a current-bucket count, and a last-seen time. Before updating these, it reads 12 features: for each key, a first-occurrence indicator, both counts, and the recency Δx=tk−Tx[qx]\Delta_x = t_k − T_x[q_x]. It adds two transforms of the current-bucket pair count, for 14 features in total. On the training slice, SimpleCount keeps the feature whose training AUROC A has the highest max(A, 1−A), together with the orientation in which A exceeds 0.5. A test edge’s anomaly score is that feature’s value, multiplied by −1 if the orientation is inverted: sk=σ∗⋅ϕk(j∗)s_k = \sigma^{*}\cdot\phi_k^{(j^*)}.

Q2: The criterion is training-slice AUROC, taken in whichever orientation exceeds 0.5. The selection needs only the training slice’s features and labels. Its output is one feature index and one sign. No test labels are used, and the sign is never re-chosen on test data. Section 3.1 now motivates these choices (highlighted in blue): we select from a pool because the informative statistic differs across datasets (Table 1), and on AUROC because it needs no threshold and needs no calibration across feature scales. Selecting on training data alone stops the reference from setting an optimistically biased bar for the models compared against it.

Thank you for the detailed response and for addressing my concerns. I appreciate the revisions and clarifications, which have adequately addressed my main points. Given these improvements, I will raise my original score.

Thank you for taking the time to read the rebuttal and improve your score!

Comments on the paper

3 comments

We thank you for the constructive review and have uploaded a revised PDF (changes in blue).

W1: We agree, and have revised this (highlighted in blue). SimpleCount and SLADE are now reported in directed AUROC. SimpleCount selects its feature and sign on the training slice and never re-chooses the sign on test data, so Reddit is reported at 0.382. The headline count does not change, because the submitted version already counted Reddit as a SLADE win. SimpleCount’s directed AUROC is at least SLADE’s on the same three datasets (Wikipedia, MOOC, Synth-Triangle). We agree with the reviewer’s reading of these three: only MOOC is a significant win, Synth-Triangle is not significant, and Wikipedia is a tie whose ordering changes across SLADE seeds (Sections 5.1 and 5.3).

Two numbers change, and we have updated both. SimpleCount now exceeds IsoForest on five of six datasets rather than six. SLADE’s mean gain where it wins is 18.5 pp rather than 10.66 pp. The unsupervised baselines MIDAS-F and IsoForest remain at effective AUC in Table 3, which can only favour them. The Table 3 caption and Appendix C state exactly where effective AUC is still used. We also see directed AUROC as the right measure for a reference: a reference whose orientation was chosen on test data would set an inflated bar for every model compared against it.

W2: We have addressed this with an extended evaluation (Appendix H, summarised in Section 5.1 and highlighted in blue). It adds GraphMixer, DyGFormer, TGN, and CAWN, evaluated as link-prediction-pretrained encoders with fitted anomaly classifiers, on all five interaction datasets alongside SLADE. It also evaluates DyGFormer on Theia and TRACE. Across these 27 comparisons, the single feature matches or exceeds neural AUROC in 20 and neural AP in 11.

The added models also show where complexity pays off. DyGFormer leads the single feature by 9.61 and 9.01 AUROC points on Bitcoin-Alpha and Bitcoin-OTC, and native SLADE leads on the two email streams. SLADE remains the only anomaly-specific self-supervised detector we evaluate, so we do not claim it represents the model class on its own. The conclusion that the benefit of complexity is dataset-dependent rests on all five neural models.

W3: We agree that the configurations are asymmetric. Both baselines use what their authors released: SLADE’s repository provides a recommended configuration for each dataset, while MIDAS-F’s provides a single demo configuration, which we kept unchanged. The revision now states that MIDAS-F is not tuned per dataset and that its results may understate what it can achieve (Section 4.3). It also limits the claim that neither MIDAS-F nor IsoForest is top-performing to their default configurations (Section 5.1). Both changes are highlighted in blue. In the extended evaluation, MIDAS-F under the same configuration is the strongest method on MIDAS DARPA, a dataset from its original evaluation (Table A4). In its native direction it also falls below chance on several other datasets there, which is consistent with your point that a fixed configuration can understate it. MIDAS-F is also not part of the headline comparison against SLADE.

W4:

  • Scale: The extended evaluation (Appendix H, highlighted in blue) adds the Theia and TRACE computer-system streams and MIDAS DARPA network traffic. These extend the evaluated streams from 672K edges to up to 10M edges (Table A3).
  • Compute: The feature extraction is a single chronological pass with constant work per edge, O(|E|) (Section 3.1). Our measured wall-clock ratios are for the six main datasets.
  • Features: The pool is deliberately limited to what per-key counters can maintain in one pass. Community-level or global structure would need extra machinery and dataset-specific choices, which works against a cheap, standard reference. A richer pool would, if anything, raise the bar the learned models must clear. The pool does include one burst-relative feature, the current-bucket pair count divided by its running mean (Section 3.1), which tracks local density shifts.

W5: Agreed. Section 6.1 now states that, with six datasets, the Gini split is a descriptive observation only (highlighted in blue). The explanation that follows it is presented as a plausible hypothesis, not a finding.

W6: The probes test one specific claim: that attention and memory models exploit multi-hop structure which per-edge counts cannot see by construction. Closure patterns isolate that claim, and the generator-informed scores confirm that the signal is present in prior edges. Temporal bursts are a different case. Count-based detectors such as MIDAS-F, and our current-bucket features, are built to catch bursts, so a burst probe would mainly test the count side rather than the structural claim. We agree that “recoverable but missed” is shown only for triangle and 4-cycle closure, and the paper states the result for those two patterns only.

Q1: Under directed AUROC the count does not change (see W1), because Reddit was already a SLADE win. The abstract now states the result in directed AUROC and reports five of six, not six of six, for IsoForest (highlighted in blue). We agree that the result is fairly described as two higher point estimates plus one tie, and Section 5.1 reports which of these differences are significant.

Q2: We have not tuned MIDAS-F per dataset. The revision now states this explicitly (Section 4.3, highlighted in blue, see W3).

Q3: See W2. We do not claim that SLADE alone represents the model class. The added models cover four design families: memory (TGN), walks (CAWN), MLP mixing (GraphMixer), and transformers (DyGFormer). The conclusion holds across them: the single feature matches or exceeds neural AUROC in 20 of 27 comparisons, while neural models lead on the Bitcoin graphs and the email streams. Our central claim is about evaluation practice, so it does not depend on any single model representing the class.

Q4: Appendix H reports the label-budget experiment you suggest: feature selection is repeated with 10%, 25%, and all development labels, averaging over three nested label subsets (highlighted in blue). With 10% of development labels, the single feature keeps its AUROC on Bitcoin-OTC and MOOC, and loses some on Wikipedia (0.887 to 0.706), Bitcoin-Alpha (0.664 to 0.611), and Reddit (0.680 to 0.564). With 25%, Bitcoin-Alpha recovers fully and Wikipedia reaches 0.820. On whether the same features are chosen: when selection moves from the training slice to a validation segment, every dataset keeps the same feature and orientation except Reddit. Reddit’s choice changes from cuc_u to −cuv−c_{uv}, and its test AUROC rises from 0.382 to 0.680 (Appendix H, highlighted in blue). We did not vary the split boundaries, so sensitivity to the split ratio remains untested.

Q5: The path-count score is a recoverability check, not a proposed baseline. Its form is chosen from knowledge of the generator, and it is not part of the detector comparison. Section 5.4 now states its cost (highlighted in blue): with hash-set neighbourhoods it needs at most du⋅dvd_u \cdot d_v set lookups per edge, so unlike the 14 features its cost grows with node degree. The negligible-compute claim applies only to the 14-feature pool. We did not time the structural scores against SLADE.

Q6: We did not consult the authors of the audited methods or datasets. On whether the recommendations are actionable: each uses artifacts a benchmark author already has.

  • The one-feature reference is a single linear-time pass on a CPU.
  • Paired tests need only the two methods’ stored test scores.
  • Wall-clock reporting needs only timers.
  • A full-feature control and synthetic probes are routine to run.

This paper carries out all five recommendations, and the code and generators are released. There is also precedent: EdgeBank’s memorization rule, proposed in a similar critique, became a standard baseline in the Temporal Graph Benchmark (Huang et al., 2023).

Thanks for the authors' responses, which address some of my issues. I will keep my score.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.