RAD: Rule-Augmented Relational Anomaly Detection

Noah Dahle, Anne Tumlin, Ngoc Tran, Xenofon Koutsoukos, Tyler Derr

Vanderbilt University

CIKM '26 · Rome, Italy

Key idea

Mine symbolic rules from the data, inject them into target nodes before graph message passing, and train a heterogeneous graph autoencoder with a ranking loss to achieve better anomaly retrieval in multi-table databases.

Overview of RAD: rule mining with random forests and LLM refinement, rule-feature augmentation, relational graph construction, heterogeneous graph autoencoder and losses. — Overview of RAD. Candidate rules come from random-forest paths and are refined into compact predicates. The resulting rule features are concatenated onto target nodes of the relational graph, and a heterogeneous graph autoencoder is trained with reconstruction and pairwise ranking losses. Click the figure for full size.

Abstract

Anomaly detection is often applied to data stored in relational databases, yet most existing methods require flattening multiple tables into a single feature matrix. This flattening can obscure entity identity, schema structure, and multi-hop dependencies, limiting the detection of anomalies that depend on relational context rather than isolated feature values. Beyond preserving relational structure, relational anomaly detection raises an additional challenge: how to incorporate symbolic behavioral evidence into learned relational representations. To address these challenges, we study relational anomaly detection, where the goal is to identify anomalous entities or events in a multi-table database. We propose RAD, a rule-augmented relational anomaly detector that combines heterogeneous graph representation learning with refined symbolic rule signals. RAD derives candidate rules from random-forest paths over flattened summaries of the entities or events being scored, refines them into compact interpretable predicates, injects the resulting rule features into the graph model, and learns anomaly scores using reconstruction-based and pairwise-ranking supervision.

To evaluate this setting, we introduce a relational anomaly detection benchmark spanning three settings: LANL cybersecurity event detection and two unexpected user-churn anomaly tasks derived from Amazon and H&M relational databases. Experiments show that RAD improves anomaly ranking over flattened tabular detectors and relational baselines under natural class imbalance, achieving the best average rank on AUROC and AUPRC across the benchmark. Ablations show that direct rule injection and ranking-based supervision are key contributors to performance, while edge reconstruction is not uniformly beneficial.

Citation

@inproceedings{dahle2026rad,
  title     = {RAD: Rule-Augmented Relational Anomaly Detection},
  author    = {Dahle, Noah and Tumlin, Anne and Tran, Ngoc and
               Koutsoukos, Xenofon and Derr, Tyler},
  booktitle = {Proceedings of the 35th ACM International Conference
               on Information and Knowledge Management (CIKM '26)},
  pages     = {909--919},
  year      = {2026},
  publisher = {ACM},
  doi       = {10.1145/3799682.3841086}
}