RAD: Rule-Augmented Relational Anomaly Detection

AI summary

Overview

• Research area: Machine learning for anomaly detection on relational databases, combining heterogeneous graph representation learning with symbolic rule mining. Published at CIKM '26 (Proceedings of the 35th ACM International Conference on Information and Knowledge Management, November 07–11, 2026, Rome, Italy), arXiv:2608.23468v1 [cs.LG].
• Technical level: Advanced. The paper assumes familiarity with graph neural networks (GraphSAGE-style message passing), graph autoencoders, pairwise learning-to-rank objectives, and rule-mining statistics such as support, confidence, and lift.
• Scope: The paper defines relational anomaly detection (ranking anomalous entities or events in a multi-table database), proposes the RAD detector, and introduces a three-task benchmark spanning LANL cybersecurity event detection plus two unexpected user-churn tasks derived from Amazon and H&M relational databases.

What This Paper Is About

Most anomaly detectors expect data as one flat feature matrix, so applying them to relational databases requires joining and aggregating multiple tables into row-level summaries. That flattening throws away entity identity, schema roles, multi-hop dependencies, and temporal context, which are often exactly what makes a relational anomaly suspicious. The authors propose RAD, which instead keeps the database as a heterogeneous graph, mines interpretable rules from an auxiliary flattened view, injects those rule features directly into the target nodes before message passing, and trains an anomaly scorer with reconstruction and pairwise-ranking objectives.

Key Contributions

1. Formalizing relational anomaly detection as a setting distinct from tabular and graph anomaly detection, where anomalousness may depend on cross-table, multi-hop, temporal, and schema-dependent interactions, with a temporal-consistency constraint that scoring may only use graph structure and attributes available at or before the target timestamp.
2. The RAD method: a rule-augmented relational anomaly detector for multi-table databases that mines rules from relational summaries, injects rule-derived binary features into target nodes, and learns anomaly scores using heterogeneous-graph representations, reconstruction, and pairwise-ranking objectives.
3. A relational anomaly detection benchmark suite combining LANL cybersecurity event detection with two unexpected user-churn tasks derived from the Amazon and H&M datasets in RelBench, providing unified target definitions, anomaly-label constructions, relational graph construction, and ranking-based evaluation protocols.
4. An empirical comparison of RAD against flattened tabular anomaly detectors, relational baselines based on Relational Deep Learning, and targeted ablations, showing that direct rule injection improves anomaly retrieval under severe class imbalance.

Main Findings

• RAD ranks anomalies best on average: Experiments show 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. (The paper content provided does not report the specific AUROC or AUPRC values.)
• Direct rule injection and ranking supervision drive performance: Ablations show that direct rule injection and ranking-based supervision are key contributors to performance.
• Edge reconstruction is not uniformly beneficial: The structure-reconstruction term has dataset-dependent effects; the no-BCE variant sets the edge-reconstruction weight to zero, and the authors state edge reconstruction "is not uniformly beneficial."
• Injection beats post-hoc fusion: Rule features are more useful when injected into the graph representation before message passing than when added after graph scoring, since post-hoc fusion cannot change the representations the encoder learns.
• LLM-assisted refinement mainly compacts rules: LLM-assisted rule refinement functions well as a compaction and deduplication step rather than as a source of new signal.
• Relational modeling plus rules help most on ranking metrics: Gains appear especially on ranking-oriented metrics such as AUPRC and precision@k, which matter because anomaly detection is usually highly imbalanced and practitioners care whether true anomalies appear near the top of the ranked list.
• Stable across anomaly prevalence: The prevalence sweep varies the filtering threshold across 0.5%, 1.5%, and 3.0% (default 1.5%) and shows RAD's ranking advantage over the supervised RDL baseline is stable across this range.
• Benchmark scale: LANL comprises 7 tables, 1.65B records, and 1.64B target authentication events; Amazon comprises 3 tables, 15.0M records, and 1.85M target customers; H&M comprises 3 tables, 16.7M records, and 1.37M target customers.

Methodology in Plain English

RAD works in four stages.

First, the relational database is converted into a heterogeneous graph: each table row becomes a node, primary-foreign key relationships become typed edges, and each node type gets its own input projection because different tables have different attributes. Graph construction respects the temporal constraint, so an earlier target node is never scored using future information.

Second, RAD builds an auxiliary flattened view of the target entities purely to discover rules. It trains a random forest classifier on that view (after removing identifier, timestamp, label, and unavailable future-information columns), then treats every root-to-leaf path as a candidate conjunctive predicate, such as "feature x is above some threshold AND feature y is below another." Candidates are scored with adapted support, confidence, and lift — confidence being the share of covered nodes that are anomalous, and lift comparing that confidence to the base anomaly prevalence in the same split. Invalid predicates, duplicates, and those referencing identifiers, labels, or future information are discarded. An optional LLM step is used only as a constrained proposer of SQL WHERE predicates that prune, tighten, combine, or generalize sampled seed rules; it never assigns labels, produces scores, introduces external attributes, or sees test labels.

Third, the surviving rules are turned into binary features — one bit per rule indicating whether a target entity satisfies it — and concatenated onto the target node's original feature vector. Non-target nodes keep their original features. This injection happens before message passing, so symbolic evidence shapes the learned embeddings rather than only adjusting final scores.

Fourth, a two-layer heterogeneous GraphSAGE encoder with relation-aware mean aggregation produces target-node embeddings, which feed three objectives: attribute reconstruction of the rule-augmented features (which also supplies the anomaly signal), an optional edge reconstruction term over observed and sampled non-edges, and a pairwise ranking loss (softplus over score differences between sampled anomalous and normal nodes). The total objective is the attribute loss plus α times the structure loss plus β times the ranking loss, with α set to zero in the no-BCE ablated variant. The final rule set is frozen after training and validation; at test time only those fixed predicates are evaluated on held-out entities.

Two derived tasks required extra label construction. For Amazon and H&M, the original RelBench churn label is filtered so a user counts as anomalous only if they churned and their prior activity history did not already signal an expected disengagement. The decline threshold adapts to each user's baseline activity level using λ0 = 0.05, λ1 = 10.0, and λ2 = 0.02. Training positives are then downsampled to a target anomaly prevalence of 1.5%, with validation downsampled to match.

Why This Matters

• Research impact: The paper separates relational anomaly detection from both tabular anomaly detection and generic graph anomaly detection, and identifies where symbolic evidence enters the model (before message passing versus after scoring) as an explicit design decision. It also contributes reusable benchmark task definitions and a unified ranking protocol built on top of existing RelBench databases and LANL.
• Real-world applications:
  • Cybersecurity: flagging authentication events that look ordinary as rows but become suspicious when linked to unusual user-machine pairs, unfamiliar process activity, or bursts of logins across many machines.
  • E-commerce customer analytics: detecting customers whose reviewing or purchasing behavior stops unexpectedly without a prior activity decline, as in the Amazon review-churn task.
  • Retail: identifying unexpected disappearance from purchase activity using customer-transaction-article links and item metadata, as in the H&M purchase-churn task.
  • General multi-table enterprise data (fraud detection, healthcare, cyber-physical systems), where records live in linked tables rather than one flat matrix.
• Industry relevance: Anomaly detection is typically severely imbalanced, so what operators need is a reliable ranked list of candidates rather than calibrated probabilities. RAD targets ranking-oriented metrics such as AUPRC and precision@k, keeps symbolic rules human-readable so analysts can inspect why a case was flagged, and offers an optional LLM refinement step that fits into existing rule-authoring workflows. Code and data are released at https://github.com/noahd15/RAD_RelationalAnomalyDetection.

Future Directions

• Determining when edge reconstruction helps and when it hurts: the authors report dataset-dependent effects and therefore treat structure reconstruction as optional, leaving the conditions for its benefit unresolved.
• Better use of LLMs in rule refinement: current results indicate the LLM functions mainly as a compaction and deduplication step rather than a source of new signal, so generating genuinely new discriminative predicates remains open.
• Extending the benchmark beyond three tasks — one cybersecurity setting and two derived e-commerce churn tasks — to other multi-table domains and anomaly definitions.
• Investigating rule features that reach beyond one-hop aggregates: for the Amazon task, mined rules were restricted to one-hop customer-level aggregates, with multi-hop product context reaching the model only through message passing rather than through rules.
• Understanding the interplay between rule injection and relational message passing more deeply, given that the encoder backbone was deliberately matched to the RDL baseline to isolate the effect of rule injection.

Target Audience

Researchers and graduate students working on anomaly detection, graph representation learning, relational deep learning, or neuro-symbolic methods; industry practitioners in security operations, fraud, and customer analytics who score entities living in multi-table databases; and data scientists who already rely on flattened feature engineering and want a way to keep schema structure and interpretable behavioral rules in the loop. Readers should be comfortable with graph neural networks and imbalanced-classification evaluation metrics.

Authors’ 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.