cs.LGAug 24, 2026

RAD: Rule-Augmented Relational Anomaly Detection

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

Organizations: Vanderbilt University Nashville, Tennessee, USA

Read PDF
Ask AI
Cite

Copy citation

DOINot available for this paper

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. Our code and data are available at: https://github.com/noahd15/RAD_RelationalAnomalyDetection.

Figures & tables

Figure 1. Overview of RAD. A database is represented by a flattened view for rule mining and a heterogeneous graph for representation learning. Random-forest paths are refined into predicates, converted into binary features, and injected into nodes before heterogeneous graph encoding. The model produces anomaly scores and ranks target nodes.
TaskDomainTargetTablesRecordsTargetsAnomaly
LANLCybersecurityAuth event71.65B1.64BRed-team auth.
AmazonE-commerceCustomer315.0M1.85MUnexpected review churn
H&MRetailCustomer316.7M1.37MUnexpected purchase churn
Table 1. Summary of the relational anomaly detection benchmark tasks. LANL is treated as a multi-table event database, while Amazon and H&M are derived from relational user-behavior databases and converted into unexpected churn anomaly detection tasks.
Figure 2. Unexpected-churn filtering. Churned users with an expected prior activity decline are removed; remaining churned users are treated as unexpected-churn anomalies. Unexpected-churn filtering keeps churned users without a prior activity decline and removes churned users with an expected decline.
SettingLANLAmazonH&M
Feature groupsAuth attrs.; user-pair novelty; recent auth., DNS, flow, processRecent reviews; rating history; product diversity; review-history spanRecent purchases; price history; article diversity; activity trend/level
Training cap500K200K200K
Forest size1200200200
Depth / leafNone / 110 / 510 / 5
Class weightBalancedBalancedBalanced
Path extractionFirst 200First 100First 100
Table 2. Feature views and random-forest rule-mining settings by dataset.
ModelTab.GraphRankSup.
Isolation Forest ( Liu et al., 2008 )✓✗✗✗
Deep SVDD ( Ruff et al., 2018 )✓✗✗✗
AE ( Sakurada and Yairi, 2014 )✓✗✗✗
AE + Rank✓✗✓✗
DRL ( Ye et al., 2025 )✓✗✗✗
RDL GNN ( Fey et al., 2024 )✗✓✗✗
Table 3. Baselines compared in our experiments, categorized by input representation and supervision signal.
 LANLAmazonH&MAvg. Rank
ModelAUROCAUPRCP@kAUROCAUPRCP@kAUROCAUPRCP@kAUROCAUPRCP@k
RAD (rules, no BCE)0.996\mathbf{0.996} ±0.001\pm 0.0010.659\mathbf{0.659} ±0.053\pm 0.0530.601\mathbf{0.601} ±0.012\pm 0.0120.6930.693 ±0.010\pm 0.0100.043\mathbf{0.043} ±0.003\pm 0.0030.0500.050 ±0.007\pm 0.0070.828\mathbf{0.828} ±0.071\pm 0.0710.143\mathbf{0.143} ±0.017\pm 0.0170.129\mathbf{0.129} ±0.022\pm 0.0222.0\mathbf{2.0}1.2\mathbf{1.2}2.0\mathbf{2.0}
RAD (rules, BCE)0.8600.860 ±0.155\pm 0.1550.557\mathit{0.557} ±0.029\pm 0.0290.572\mathit{0.572} ±0.008\pm 0.0080.6950.695 ±0.010\pm 0.0100.043\mathbf{0.043} ±0.004\pm 0.0040.051\mathit{0.051} ±0.004\pm 0.0040.787\mathit{0.787} ±0.074\pm 0.0740.110\mathit{0.110} ±0.020\pm 0.0200.125\mathit{0.125} ±0.022\pm 0.0223.3\mathit{3.3}1.8\mathit{1.8}2.3\mathit{2.3}
RDL weighted ( Fey et al., 2024 )0.5530.553 ±0.158\pm 0.1580.0070.007 ±0.014\pm 0.0140.0210.021 ±0.064\pm 0.0640.720\mathbf{0.720} ±0.002\pm 0.0020.037\mathit{0.037} ±0.000\pm 0.0000.062\mathbf{0.062} ±0.004\pm 0.0040.7000.700 ±0.005\pm 0.0050.0350.035 ±0.001\pm 0.0010.064\mathit{0.064} ±0.013\pm 0.0134.74.74.84.83.73.7
RDL unweighted ( Fey et al., 2024 )0.6850.685 ±0.205\pm 0.2050.0150.015 ±0.028\pm 0.0280.0260.026 ±0.078\pm 0.0780.713\mathit{0.713} ±0.002\pm 0.0020.037\mathit{0.037} ±0.001\pm 0.0010.062\mathbf{0.062} ±0.005\pm 0.0050.6930.693 ±0.019\pm 0.0190.0390.039 ±0.004\pm 0.0040.064\mathit{0.064} ±0.016\pm 0.0164.34.33.83.83.33.3
AE+Rank ( Sakurada and Yairi, 2014 )0.9430.943 ±0.035\pm 0.0350.5250.525 ±0.078\pm 0.0780.5400.540 ±0.065\pm 0.0650.5180.518 ±0.014\pm 0.0140.0160.016 ±0.001\pm 0.0010.0150.015 ±0.003\pm 0.0030.4560.456 ±0.024\pm 0.0240.0130.013 ±0.000\pm 0.0000.0050.005 ±0.004\pm 0.0045.25.25.25.25.75.7
Table 4. Main results across datasets over 10 seeds. Results are reported as mean ±\pm standard deviation. Avg. rank columns report the average rank per metric across datasets; lower is better.
Figure 3. Rule-construction and structure-reconstruction ablations across datasets over 10 seeds. Bars show means and error bars show standard deviations. The y-axis is broken to separate AUROC from smaller AUPRC and P@k values. Rule-construction and structure-reconstruction ablation results across datasets over ten seeds. Bars show mean AUROC, AUPRC, and precision at k with standard-deviation error bars.
Figure 4. Label-prevalence sensitivity for unexpected-churn detection. AUROC uses the left axis and AUPRC the right axis for target prevalences of 0.5%, 1.5%, and 3.0%; counts show retained positives. Prevalence sensitivity results for Amazon and H&M comparing RAD and supervised RDL at 0.5, 1.5, and 3.0 percent anomaly prevalence.

Explore similar work

CardsList
Jun 17, 2026

Towards Anomaly Detection on Relational Data

Relational databases are widely used for managing structured data in real-world systems. Detecting anomalies from such relational data is crucial for identifying fraud, risks, and abnormal behaviors, yet remains under-explored. The key challenges lie in the intrinsic complexity of relational data: multi-table attributes are high-dimensional and heterogeneous, making sparse abnormal clues easy to overwhelm by normal or irrelevant information; and anomalies may further manifest as abnormal connection patterns across different foreign-key relations, which existing tabular and graph anomaly detection methods are ill-suited to capture. To address them, we propose RelAD, a reconstruction-based framework that captures anomalies from both attribute and relational edge reconstruction. RelAD contains two core modules: conditional sparse-gated attribute reconstruction, which suppresses redundant multi-table attributes and emphasizes abnormal semantic blocks, and dual-view multi-relational edge reconstruction, which detects relation-specific abnormal connections from both intrinsic and behavioral entity profiles. The resulting attribute and relational signals are integrated through a lightweight fusion module to produce the final anomaly score. We further construct 6 benchmark datasets with systematic anomalies, on which extensive experiments show that RelAD consistently outperforms other baselines while achieving competitive efficiency.

Shiyuan Li, Yunfeng Zhao, Yue Tan +3

Griffith University · Guangxi University

Reconstruction-Based Anomaly DetectionRelational DatabasesAnomaly Detection
AskPDF
Jun 27, 2026

RGLD: Randomized Global-Local Density Estimation for Tabular Anomaly Detection

Unsupervised tabular anomaly detection requires methods that are accurate, robust across heterogeneous datasets, and computationally efficient. Classical statistical detectors are often efficient, but they usually rely on a fixed data view and a single notion of abnormality. Deep anomaly detectors can learn more flexible scoring functions, but they are substantially slower and difficult to tune in unsupervised settings due to the lack of a reliable supervisory signal. We propose RGLD, a randomized global-local density estimator for efficient unsupervised tabular anomaly detection. RGLD combines a global random-feature density branch, which identifies samples in broadly low-density regions, with a local neighbor branch, which detects samples that are weakly supported by nearby observations. Both branches operate over feature-bagged randomized views, allowing RGLD to expose anomaly evidence that may be hidden in any single representation. We conduct experiments on 47 tabular datasets against 23 statistical and deep anomaly detection baselines under fully unsupervised setting. RGLD achieves the strongest dataset-level AUROC performance, ranking 1st in dataset wins, and ranks 2nd in AUPRC wins. RGLD is also faster than all evaluated deep detectors, achieving 50x-580x speedups, and remains competitive with statistical methods in runtime, yielding a favorable accuracy-efficiency tradeoff.

Quanling Zhao, Jiaying Yang, Ye Tian +5

1Computer Science and Engineering, University of California San Diego · 2Intel Corporation

Tabular Anomaly DetectionUnsupervised Anomaly DetectionAnomaly Detection
AskPDF
Mar 18, 2026

Unsupervised Symbolic Anomaly Detection

We propose SYRAN, an unsupervised anomaly detection method based on symbolic regression. Instead of encoding normal patterns in an opaque, high-dimensional model, our method learns an ensemble of human-readable equations that describe symbolic invariants: functions that are approximately constant on normal data. Deviations from these invariants yield anomaly scores, so that the detection logic is interpretable by construction, rather than via post-hoc explanation. Experimental results demonstrate that SYRAN is highly interpretable, providing equations that correspond to known scientific or medical relationships, and maintains strong anomaly detection performance comparable to that of state-of-the-art methods.

Md Maruf Hossain, Tim Katzke, Simon Klüttermann +1

TU Dortmund University, Dortmund, Germany · Research Center Trustworthy Data Science and Security, UA Ruhr, Germany

Unsupervised Anomaly DetectionAnomaly DetectionInterpretable Anomaly Detection
AskPDF