PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Omair Shafi Ahmed, Zohair Shafi

arXiv:2608.15965v1cs.LG

TL;DR

The paper asks whether increasingly complex temporal-graph anomaly detectors deliver gains beyond simple references. It evaluates a no-fitting one-feature baseline and finds that complexity is dataset-dependent, while SLADE uses substantially more compute.

  • Problem

    How much anomaly-detection improvement comes from added architectural complexity remains unclear despite increasingly elaborate temporal-graph models.

  • Method

    SimpleCount selects one scalar feature per dataset and is compared with MIDAS-F, SLADE, and IsoForest across six datasets using chronological selection, paired tests, and synthetic probes.

  • Results

    SimpleCount matches or beats SLADE on three of six datasets, exceeds IsoForest on all six, and uses 23–133× less wall time than SLADE.

  • Takeaways & Limitations

    Complexity is dataset-dependent, so reported detector gains should be benchmarked against a strong one-feature reference alongside compute cost.

  • Takeaways & Limitations

    The synthetic structural-score test uses only neighbors observed before each event and excludes anomaly labels and future edges.

Abstract

from arXiv · show

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 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 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 133x more wall-clock time than SimpleCount. On Synth-Triangle and an additional Synth-Quad probe, pre-event structural scores recover the planted signal at AUC up to 0.955, while all evaluated detector models remain near random. 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.

1 Introduction

SimpleCount tests whether added complexity improves streaming-graph anomaly detection by comparing a one-feature, no-fitting reference with learned detectors and IsoForest. Across six datasets, it is competitive with SLADE, surpasses IsoForest, costs far less compute, and supports reporting gains against strong simple baselines.

  • Evaluation design: SimpleCount selects one scalar feature per dataset, while MIDAS-F and SLADE provide learned-detector comparisons and IsoForest tests nonlinear use of all 14 features.The evaluation also includes a separate two-dataset GraphMixer check because its downstream classifier uses anomaly labels.
  • Accuracy: 3 of 6 datasets show SimpleCount matching or beating SLADE, while SimpleCount exceeds IsoForest on all six by AUC.The datasets comprise five public datasets and one synthetic dataset.
  • Interpretability: SimpleCount detections are directly traceable to an observed count, recency, or first-occurrence value, unlike feature ensembles or learned latent node states.This one-feature attribution does not require an explanation method such as SHAP.
  • Takeaway: The benefit of complexity is dataset-dependent, so claimed gains should be reported against a strong one-feature reference together with compute cost.The paper distils this audit into five recommendations for benchmark authors and reviewers in Appendix A.

2 Related Work

The paper combines temporal-graph anomaly detection with evidence that strong simple baselines can rival specialized models. It extends this baseline-first perspective with paired inference and compute-cost accounting.

  • The work connects temporal-graph anomaly detection with benchmark studies on strong simple baselines, adding paired inference and compute-cost accounting.
  • Temporal-graph anomaly detection: Temporal-graph anomaly detection includes MIDAS-F, SedAnSpot, FFADE, and SLADE, which combines node memory, a GRU updater, a TGAT memory generator, and self-supervised objectives.
  • Simple baselines: EdgeBank showed that a hash-set of seen edges matches or outperforms TGN, TGAT, CAWN, and JODIE on multiple temporal link-prediction benchmarks.
  • Corrective benchmark critiques in graph learning: Prior graph-learning critiques found that simple methods can rival specialized models, including tree ensembles outperforming specialized GNN anomaly detectors on static graphs.
  • Parsimony audits in machine learning: Lipton and Steinhardt warned that gains attributed to new methods often stem from hyperparameter tuning rather than the methods themselves.

3 Methodology

The methodology establishes a low-complexity one-feature reference with chronological, leakage-resistant feature extraction and selection, paired statistical testing, and synthetic probes of planted graph patterns. It evaluates whether detector models recover structures available from graph history without using labels or future edges.

  • Measurement protocol: The protocol combines a one-feature reference, chronological feature selection, paired significance tests, and synthetic probes of planted graph patterns.These four components define the measurement protocol.
  • Chronological features: A single chronological pass maintains lifetime and time-bucket counts plus most-recent timestamps for each source, destination, and ordered pair.Time-bucket counts reset when the stream enters a new bucket.
  • Chronological features: B = 1000 equal-width intervals are used, and every edge feature is computed before that edge updates maintained state.Thus, each feature vector depends only on earlier edges.
  • Feature selection: For each dataset, the feature with the highest effective training AUC, max(AUCtrain, 1 −AUCtrain), is selected and evaluated using orientation-invariant test separability, max(AUCtest, 1 −AUCtest).Selection uses the chronological training slice.
  • Statistical testing: Paired DeLong correlated-ROC and paired permutation tests account for statistical dependence because methods score the same held-out edges against the same labels.The ROC-AUC estimates are therefore not treated as independent.
  • Synthetic probes: The synthetic experiment plants p = 0.01 anomalies that close existing two-hop paths and tests recovery with a pre-event common-neighbor score using only graph history.The score uses no anomaly labels or future edges, and it is separate from the detector-model comparison.

4 Experimental Setup

The experiments compare four unsupervised methods on five public datasets and one generated probe under a shared chronological evaluation protocol. Paired rank-based tests address dataset-specific score orientation and severe class imbalance.

  • Protocol: All methods use the same edge streams, chronological split, and evaluation metric, with SimpleCount selected on the chronological training slice.The five real interaction datasets and Synth-Triangle use B = 1000 equal-width time intervals.
  • Datasets: Five public datasets and one generated probe are evaluated: Wikipedia, MOOC, Reddit, Bitcoin-Alpha, Bitcoin-OTC, and Synth-Triangle.Wikipedia, MOOC, and Reddit come from JODIE; Bitcoin-Alpha and Bitcoin-OTC are signed trust networks.
  • Statistical tests: Paired DeLong tests are used for five datasets, while Reddit uses a paired permutation test because the score orientation reverses on its test slice.Both tests compare methods on identical test edges and labels.
  • Evaluation: Positive rates span 0.05%-7.22%, so ROC-AUC and paired rank-based inference are used because they remain valid regardless of base rate.The inference operates on per-edge score orderings rather than threshold-dependent metrics.
  • Methods: Four methods are evaluated on every dataset: SimpleCount, MIDAS-F, SLADE, and IsoForest.SimpleCount selects one scalar from a fixed 14-feature pool, while IsoForest fits the complete 14-dimensional vector.

5 Results

SimpleCount matches or exceeds SLADE on three of six datasets and exceeds IsoForest on all six, while requiring substantially less computation. Synthetic probes show that pre-event structural scores recover planted closure signals that the evaluated detector models miss.

  • Benchmark comparison: 3/6 datasets: SimpleCount matches or exceeds SLADE, and it exceeds IsoForest on all six benchmarks.SLADE wins on Bitcoin-Alpha, Bitcoin-OTC, and Reddit; the complete 14-feature IsoForest does not improve on the selected scalar feature.
  • Complexity and cost: 23–133× is SLADE’s wall-clock cost relative to SimpleCount, averaging 72× across six datasets.Where SLADE leads, its mean cost is 91× for a mean AUC gain of 10.66 pp.
  • Robustness: 0.002–0.012 is SLADE’s five-seed sample-standard-deviation range, with winner direction stable on five datasets.Wikipedia is near-tied, and its numerical ordering between SLADE and SimpleCount changes across seeds.
  • Synthetic probes: 0.666 AUC is achieved by the pre-event common-neighbor score on Synth-Triangle, while all tested detector models remain near chance at 0.50–0.57.The score uses prior edges without labels or future edges and reveals the planted two-hop structure; the +14 pp gap shows SLADE misses it.
  • Synthetic probes: 0.955 AUC is achieved by the pre-event length-3 path-count score on Synth-Quad, versus 0.506 for SLADE and 0.557 for SimpleCount.The score has a paired-DeLong margin of +0.45 over SLADE and +0.40 over SimpleCount; the 2-hop common-neighbor score is 0.508.
  • Implementation and features: 18 000–37 000 edges/sec is SimpleCount’s one-core CPU throughput, versus 140–1 560 edges/sec for SLADE on an H100 GPU.SimpleCount selects source count cu on Wikipedia, MOOC, and Reddit, and destination count cv on Bitcoin-Alpha and Synth-Triangle.

6 Discussion

Added complexity helps selectively: SLADE gains accuracy on some datasets, but SimpleCount matches or exceeds it elsewhere, especially where destination activity is less concentrated. The MOOC result illustrates how a simple activity-based feature can directly capture the label pattern that a temporal representation objective may suppress.

  • Compute–accuracy trade-off: 13.7 pp AUC is SLADE’s strongest trade-off on Reddit, achieved at a 23× wall-clock premium over SimpleCount.On Bitcoin-Alpha and Bitcoin-OTC, SLADE gains 8–10 pp AUC, while added compute does not improve AUC on Wikipedia, MOOC, or Synth-Triangle.
  • Dataset structure: 0.55 destination-activity Gini separates the datasets: SLADE leads on the three higher-Gini datasets, while SimpleCount matches or exceeds it on the three lower-Gini datasets.Concentrated destination activity may create hub-related interaction patterns available to attention mechanisms but absent from a one-dimensional feature.
  • MOOC dropout signal: −cu, the inverted lifetime source interaction count, is selected for MOOC and assigns higher anomaly scores to interactions from users with fewer prior interactions.Because users who leave after very few sessions are labelled dropouts, the feature directly captures the label pattern.
  • MOOC dropout signal: SLADE’s contrastive objective may suppress MOOC activity differences by encouraging node representations to drift minimally over time.This provides a possible reason the simple activity-based score captures the dropout signal more directly.

7 Conclusion

Across five public and one generated dataset, SimpleCount challenges the need for added temporal-graph detector complexity: it exceeds IsoForest on all six datasets and matches or exceeds SLADE on three. Complexity is dataset-dependent and should be reported alongside compute cost.

  • 7 Conclusion: SimpleCount exceeds IsoForest on all six datasets and matches or exceeds SLADE on three.The comparison evaluates a no-parameter-fitting one-feature reference against temporal-graph detector models and IsoForest.
  • 7 Conclusion: 72× is SLADE’s mean wall-clock cost relative to SimpleCount across all six datasets.Complexity earns its cost on the small Bitcoin graphs, where SLADE recovers signal absent from the selected feature.
  • 7 Conclusion: Every claimed gain should be reported against a strong one-feature reference together with its compute cost.The conclusion recommends pairing performance claims with the cost required to obtain them.

A Recommendations for benchmark authors · B Destination-activity Gini

The section recommends stronger temporal-graph anomaly-detection evaluations, including a chronologically selected one-feature baseline and paired significance tests. It also defines destination-activity Gini over observed destination nodes, where higher values indicate greater concentration.

  • A Recommendations for benchmark authors: The audit proposes five additions to future temporal-graph anomaly-detection evaluations.
  • A Recommendations for benchmark authors: A chronologically selected one-feature baseline should be reported alongside learned models.The feature is selected from prior-interaction counts, recencies, novelty indicators, and count-derived transforms.
  • A Recommendations for benchmark authors: Three of six datasets saw the one-feature baseline match or beat SLADE.
  • A Recommendations for benchmark authors: Paired significance tests should supplement seed confidence intervals in benchmark reports.The passage names the paired DeLong test, or a paired permutation test when score direction is part of the analysis.
  • B Destination-activity Gini: Destination activity is counted for each node that appears at least once as a destination.Repeated interactions count separately, while nodes never appearing as destinations are excluded.
  • B Destination-activity Gini: The destination-activity Gini is defined over the n observed destination nodes.
  • B Destination-activity Gini: A destination-activity Gini value of 0 indicates equal activity, whereas larger values indicate greater concentration.

C Evaluation protocol · D Reddit paired permutation test

The evaluation uses chronological train/test splits, effective ROC-AUC, paired significance testing, and Holm–Bonferroni correction across datasets. For Reddit, the paired permutation test yields p = 0.0027 for the SimpleCount–SLADE comparison.

  • C Evaluation protocol: An 85/15 chronological train/test split is applied to every dataset, with SimpleCount selecting features only from the training slice.
  • C Evaluation protocol: DeLong correlated-ROC tests compare per-edge scores on shared test slices, while Reddit uses a paired orientation-invariant permutation test.
  • C Evaluation protocol: The six SLADE-versus-SimpleCount dataset comparisons use Holm–Bonferroni correction with family-wise α = 0.05.
  • D Reddit paired permutation test: For Reddit, scores are converted to normalized within-method midranks, and paired labels are independently exchanged per edge with probability 1/2 across B = 9,999 replicates.
  • D Reddit paired permutation test: E = 26 produces p = (26 + 1)/(9,999 + 1) = 0.0027 under the standard add-one correction for Reddit.

E GraphMixer comparison

GraphMixer is evaluated through temporal-link pretraining followed by anomaly-label node classification. Against SimpleCount, GraphMixer trails on Wikipedia but leads on Reddit, with effective ROC-AUC reported across five seeds.

  • Evaluation pipeline: GraphMixer uses temporal-link pretraining followed by a node classifier trained on anomaly labels.The evaluation uses the DyGLib dynamic-node-classification pipeline.
  • Dataset results: 2.3 percentage points: GraphMixer trails SimpleCount on Wikipedia.The reported comparison is in ROC-AUC.
  • Dataset results: 2.1 points: GraphMixer leads SimpleCount on Reddit.Table A1 reports effective ROC-AUC, with GraphMixer summarized as mean ± sample standard deviation over five seeds.

F Precision-recall robustness · G Supplementary figures

Average-precision results preserve the three-of-six pattern while changing which datasets favor SLADE or SimpleCount, including a Bitcoin-OTC reversal. Supplementary figures visualize paired uncertainty, seed variation, and model gaps.

  • G Supplementary figures: Figure A1 reports paired DeLong forest intervals for MIDAS-F, IsoForest, and SLADE across five datasets, omitting Reddit because it uses a paired permutation test.Intervals show method AUC − SimpleCount AUC with 95% confidence intervals; hollow markers indicate unadjusted p ≥ 0.05.
  • F Precision-recall robustness: Three-of-six remains unchanged under AUPRC, but the winning datasets change relative to the ROC-AUC comparison.AUPRC uses the same deterministic scores, while SLADE values are five-seed means and chance equals each test-slice base rate.
  • F Precision-recall robustness: SLADE leads Wikipedia, Bitcoin-Alpha, and Reddit, whereas SimpleCount leads Bitcoin-OTC, MOOC, and Synth-Triangle under AUPRC.
  • F Precision-recall robustness: 0.088 and 0.064 are the two highest test-slice base rates for Bitcoin-OTC and Bitcoin-Alpha, respectively.These base rates define the AUPRC chance levels for the corresponding datasets.
  • F Precision-recall robustness: Bitcoin-OTC reverses from a SLADE win on ROC-AUC to a SimpleCount win under AUPRC.
  • G Supplementary figures: Figure A2 compares SimpleCount bootstrap 95% confidence intervals with SLADE five-seed means and sample standard deviations.SLADE’s sample standard deviation ranges from 0.002 to 0.012, with gray connectors emphasizing per-dataset gaps.
Loading 2608.15965v1…