PaperlayerView exact revision on arXiv

Source-linked AI summary

RAD: Rule-Augmented Relational Anomaly Detection

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

arXiv:2608.23468v1cs.LGcs.CRcs.DB

TL;DR

Relational anomaly detection is difficult because flattening multi-table data can discard context, while symbolic behavioral evidence is often separate from learned relational representations. RAD combines heterogeneous graph learning with injected rule features and ranking-based supervision, and improves anomaly retrieval across LANL, Amazon, and H&M settings. The paper concludes that representation, scoring, and behavioral evidence should be treated jointly, while edge reconstruction is optional rather than uniformly beneficial.

  • Problem

    Flattening relational databases can obscure entity identity, schema structure, and multi-hop dependencies, while relational learning alone may not capture symbolic behavioral patterns needed for anomaly ranking.

  • Method

    RAD converts relational databases into heterogeneous graphs, mines and refines rules from flattened target summaries, injects rule features into target nodes, and learns scores with reconstruction and pairwise-ranking objectives.

  • Results

    RAD improves anomaly retrieval under class imbalance across LANL cybersecurity event detection, Amazon review churn, and H&M purchase churn, especially on AUPRC.

  • Takeaways & Limitations

    Relational anomaly detection is best treated as a joint problem of representation, scoring, and behavioral evidence, with direct rule injection contributing to the learned representations.

  • Takeaways & Limitations

    RAD requires labeled data for rule mining and ranking, and its evaluations include held-out validation partitions, sampled LANL subgraphs, and a derived unexpected-churn label.

Abstract

from arXiv · show

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.

1 Introduction

Relational anomaly detection targets entities or events whose abnormality depends on cross-table context that flattening can obscure. RAD combines heterogeneous graph representations with mined symbolic rules and evaluates the approach across cybersecurity and user-churn tasks.

  • Motivation: Relational databases connect multiple entity and event types through primary-foreign key relationships, making some anomalies dependent on relational context.An authentication event can appear normal alone but suspicious when linked to an unusual user-machine pair.
  • Motivation: Flattening tables into row-level feature matrices can obscure entity identity, schema roles, multi-hop dependencies, and temporal context.These losses make cross-table anomalies difficult to detect with isolated feature vectors.
  • Research gap: Relational anomaly detection must preserve database structure while incorporating symbolic behavioral evidence that relational message passing may miss.Rules can encode suspicious combinations of events, entities, or activities.
  • RAD: RAD represents databases as heterogeneous graphs, mines rules from an auxiliary flattened view, injects rule features into target nodes, and learns anomaly scores.Its evaluation uses reconstruction-based and pairwise-ranking objectives with GraphSAGE-style message passing.
  • Evaluation: The benchmark combines LANL cybersecurity event detection with unexpected user-churn tasks derived from Amazon and H&M datasets.The evaluation compares RAD with tabular and relational baselines and targeted ablations under severe class imbalance.

2 Related Work

Prior methods address tabular scoring, graph structure, relational learning, or symbolic evidence separately. RAD positions relational anomaly detection as a ranking problem requiring structured representations and integrated behavioral rules.

  • Tabular anomaly detection: Tabular anomaly detectors assume independent feature vectors, but flattening relational databases compresses identity, schema roles, multi-hop dependencies, and temporal context.This representation is mismatched to anomalies whose suspiciousness depends on connected entities or history.
  • Graph and relational learning: Graph anomaly methods combine attributes and structure but usually treat data as generic graphs rather than typed relational databases.Relational databases require distinctions among table and relation types for anomaly interpretation.
  • Research gap: Relational learning preserves multi-table structure but typically lacks anomaly-specific scoring and protocols for ranking rare positives under severe class imbalance.RAD’s benchmark adapts LANL, Amazon, and H&M settings to unified anomaly-ranking tasks.
  • Symbolic evidence: Symbolic rules expose interpretable behavioral patterns, while neural relational models learn expressive embeddings; prior approaches often keep these components separate.RAD addresses this separation by injecting rule features into target nodes before message passing.
  • Findings: RAD’s broader findings indicate that edge reconstruction is not uniformly beneficial and LLM-assisted refinement mainly compacts and deduplicates rules.These findings are reported as independent of RAD’s specific architecture.

3 Preliminaries

The paper models a relational database as typed tables and converts primary-foreign key relationships into a heterogeneous graph. Target rows become target nodes whose attributes and relational context support anomaly scoring.

  • Database representation: A relational database consists of typed tables whose schema specifies attributes, primary keys, foreign keys, and relationships.Rows may represent entities or events such as users, machines, authentication events, customers, reviews, or transactions.
  • Graph representation: The database-to-graph construction maps each row to a node and each primary-foreign key relationship to a typed edge.Node and edge types preserve schema-defined distinctions for message passing.
  • Target instances: A designated target table determines which rows are scored, with target types varying across LANL, Amazon, and H&M settings.LANL targets authentication events, whereas Amazon and H&M target users or customers.

4 Problem Definition

Relational anomaly detection learns scores for target nodes so anomalous nodes rank above normal nodes. The formulation separates labeled training targets from held-out evaluation and can enforce temporal consistency.

  • Definition: The task is to learn an anomaly scoring function over target nodes using a relational database, schema, heterogeneous graph, and labeled training subset.The target table and graph provide the structured objects being scored.
  • Ranking objective: For labeled targets, the desired ranking satisfies s(v_i) > s(v_j) when v_i is anomalous and v_j is normal.This expresses anomaly detection as ordering rather than calibrated classification.
  • Evaluation: The learned scoring function is evaluated on a held-out test subset disjoint from the training targets.The formulation explicitly separates V_train and V_test.
  • Temporal consistency: When timestamps are available, scoring may use only graph structure and attributes observed at or before the target time.This temporal constraint prevents future information from entering earlier target representations.

5 RAD: Rule-Augmented Relational Anomaly Detection

RAD separates symbolic rule discovery from relational representation learning: it mines predicates from a flattened auxiliary view, then injects them into a heterogeneous graph model for anomaly scoring.

  • Architecture: RAD converts relational databases into a heterogeneous graph while retaining an auxiliary flattened view exclusively for interpretable rule discovery.The graph preserves entity types and schema-defined relationships; flattening does not replace relational representation learning.
  • Rule Mining: Random-forest root-to-leaf paths become conjunctive candidate predicates composed of feature-threshold conditions.Each path is traced from leaf to root, with splits contributing conditions such as x_j≤c or x_j>c.
  • Rule Validation: RAD evaluates predicates using support, confidence, and lift, then filters invalid, unavailable, duplicate, or insufficient-coverage rules before ranking them.Confidence is set to zero when its denominator is zero, and rule selection uses training or validation data.
  • Rule Refinement: Optional LLM refinement proposes constrained SQL WHERE predicates that are validated and rescored before the highest-ranked valid rules are retained.The LLM proposes rule transformations but does not assign labels or anomaly scores.
  • Rule Features: The final rule set is frozen before testing, and each retained predicate becomes a binary feature aligned with the corresponding target node.Held-out entities are evaluated without test-label-driven rule mining, selection, threshold relaxation, or updating.

5.3 Rule-Augmented Node Features

RAD injects binary rule vectors into target-node features before heterogeneous message passing, allowing symbolic evidence to shape embeddings alongside attributes and typed relational neighborhoods.

  • Rule-Augmented Node Features: RAD evaluates the selected rules for each target entity to produce a binary rule vector r(v).Each vector entry indicates whether the target entity satisfies one selected rule.
  • Rule-Augmented Node Features: The model concatenates each target node’s original features with its rule vector, while non-target nodes retain their original features.Rule augmentation is applied only to target nodes before graph encoding.
  • Design Choice: Direct injection lets rule evidence influence message passing and representation learning rather than merely adjusting final anomaly scores.This differs from post-hoc fusion, which cannot change representations already learned by the graph encoder.
  • Graph Encoding: A heterogeneous encoder uses type-specific projections and relation-aware message passing to combine rule-augmented features with typed relational context.Messages are aggregated separately by relation type before being combined.
  • Graph Encoding: The implementation uses a two-layer heterogeneous GraphSAGE encoder with mean aggregation, producing target embeddings for reconstruction and ranking objectives.The encoder is inductive and stable under variable-degree sampled neighborhoods.

5.5 Anomaly Scoring and Training Objective

RAD combines reconstruction-based anomaly signals with pairwise ranking supervision, optionally adding edge reconstruction to learn rule-aware relational representations while prioritizing anomaly ordering.

  • Attribute Reconstruction: RAD uses a graph autoencoder whose attribute decoder reconstructs rule-augmented target-node features from target embeddings.Reconstruction preserves target attributes and rule features while providing an anomaly signal.
  • Attribute Reconstruction: Nodes that violate common attribute, rule, or relational patterns should be harder to reconstruct.The resulting reconstruction error contributes to anomaly scoring.
  • Edge Reconstruction: Optional edge reconstruction predicts typed-edge existence from node embeddings using binary cross-entropy over observed edges and sampled non-edges.The edge term models relational graph structure in addition to target-node attributes.
  • Edge Reconstruction: Edge reconstruction is optional because it may help unusual-link anomalies but may also overemphasize sampled graph topology.RAD evaluates BCE and no-BCE variants, with the no-BCE variant setting the edge-reconstruction weight to zero.
  • Ranking Supervision: Pairwise ranking samples anomalous-normal node pairs and encourages anomalous nodes to receive higher anomaly scores.This objective targets anomaly ranking rather than calibrated binary prediction under class imbalance.
  • Training Objective: The full objective weights edge reconstruction with α and ranking supervision with β while retaining reconstruction for rule-aware relational representation learning.Setting α=0 yields the no-BCE ablation.

6 Relational Anomaly Detection Benchmark

The benchmark evaluates relational anomaly ranking across one cybersecurity event task and two unexpected-churn tasks, using criteria that preserve relational context and rare-positive evaluation. Amazon and H&M churn labels are filtered to retain only unexpected disengagement, with prevalence sensitivity tested across multiple rates.

  • Benchmark suite: The benchmark contains LANL authentication-event detection plus Amazon and H&M unexpected-churn tasks derived from relational databases.Amazon and H&M are adapted into anomaly tasks under a unified relational anomaly detection protocol.
  • Benchmark criteria: Suitable tasks require linked tables, a defined target, anomaly labels or principled label construction, rare positives, and temporal information when needed to prevent leakage.
  • Unexpected-churn construction: Unexpected-churn anomalies are churned users whose prior activity does not indicate an expected disengagement pattern.Users with an expected prior activity decline are removed from the positive anomaly class.
  • Unexpected-churn construction: The activity-decline threshold adapts to each user’s baseline activity level rather than applying one fixed cutoff.The experiments use λ0 = 0.05, λ1 = 10.0, and λ2 = 0.02.
  • Robustness evaluation: The default unexpected-churn prevalence is 1.5%, with 0.5% and 3.0% used to test sensitivity while holding the protocol and model design fixed.The sweep changes the anomaly-label filtering rate while preserving graph construction, feature views, architecture, and evaluation protocol.
  • Feature views: Dataset-specific flattened views support rule mining while RAD continues to use the relational graph for representation learning.Table 2 summarizes feature views and random-forest rule-mining settings by dataset.

7 Experiments

The experiments compare RAD with flattened tabular, relational graph, and supervised baselines on held-out target entities. They evaluate ranking quality with AUROC, AUPRC, and precision@k under severe class imbalance, while testing architectural and supervision choices.

  • Research questions: The experiments test RAD against tabular and relational baselines and examine rule features, edge reconstruction, LLM-assisted refinement, and unexpected-churn prevalence sensitivity.
  • Evaluation setup: Experiments evaluate continuous anomaly scores on held-out target entities aligned across graph and flattened representations.Each setting scores LANL authentication events or Amazon and H&M customers, using shared target populations and splits.
  • RAD configuration: RAD uses a relation-aware GraphSAGE encoder with attribute reconstruction, optional edge reconstruction, pairwise ranking, and validation-AUPRC-based model selection.The encoder has two layers and hidden dimension 128; edge reconstruction is controlled by the structure weight α.
  • Baselines: The baselines span flattened tabular detectors, graph-based relational models without rule augmentation, and a supervised MLP using ground-truth training labels.This separates input representation from supervision signal in the comparison.
  • Metrics: AUROC measures global ranking quality, AUPRC measures precision-recall performance, and precision@k measures true anomalies among the top-ranked targets.The number of positives in the test set determines k, and AUPRC and precision@k are emphasized under severe class imbalance.

8 Results

Across LANL, Amazon, and H&M, RAD improves anomaly retrieval by combining relational graph modeling with rule-derived behavioral evidence, though gains vary by dataset and auxiliary objective. Results emphasize AUPRC and precision@k because the tasks are highly imbalanced.

  • RAD achieves the strongest average AUPRC rank across the benchmark, with especially clear gains on LANL.On LANL, it substantially outperforms flattened tabular detectors and relational baselines on AUPRC and precision@k.
  • On Amazon, supervised RDL achieves stronger AUROC and precision@k, while RAD achieves higher AUPRC; on H&M, RAD leads across all three metrics.These results show that model rankings depend on the evaluation metric and dataset.
  • Rule-augmented RAD variants generally improve anomaly retrieval over variants without rule features, especially on AUPRC and precision@k.The results attribute this improvement to symbolic predicates providing behavioral evidence beyond target-node attributes and relational graph structure.
  • Compact predicate-based rules are more useful than raw decision-feature injection, while random-forest path rules already provide meaningful anomaly signal.LLM-assisted refinement mainly filters, tightens, and compacts candidate predicates before graph injection.
  • Edge reconstruction is dataset-dependent: the no-BCE variant is strongest overall, while BCE and no-BCE perform similarly on Amazon.On LANL and H&M, disabling BCE produces stronger results, suggesting edge reconstruction can overemphasize noisy sampled-subgraph artifacts.
  • Across 0.5%, 1.5%, and 3.0% churn prevalences, the main performance trends remain broadly stable, supporting 1.5% as the default benchmark configuration.The prevalence filter remains a design choice, and LANL uses sampled subgraphs rather than the full authentication log.

9 Conclusion

RAD addresses relational anomalies by combining heterogeneous graph representations with injected symbolic behavioral rules and anomaly-specific supervision. Across three tasks, it improves anomaly retrieval under class imbalance, while scalability, temporal modeling, and richer rule discovery remain open directions.

  • 9 Conclusion: Flattening can obscure relational dependencies, while relational representation learning alone lacks explicit behavioral evidence and anomaly-specific scoring objectives.RAD is designed around the joint need to preserve database structure, represent behavioral patterns, and score anomalies.
  • 9 Conclusion: RAD combines heterogeneous graph learning, mined symbolic rule features, reconstruction-based scoring, and ranking-based anomaly supervision.Rule features are injected into target nodes before message passing, allowing symbolic evidence to shape learned relational representations.
  • 9 Conclusion: Across LANL, Amazon, and H&M, RAD improves anomaly retrieval under class imbalance, especially on AUPRC.The results support treating relational anomaly detection as a joint problem of representation, scoring, and behavioral evidence.
  • 9 Conclusion: Scaling to larger databases and longer temporal histories will require more efficient graph construction and inference.The paper identifies scalability and temporal modeling as key challenges for extending RAD.
  • 9 Conclusion: Future extensions include unsupervised rule discovery, rules over complex multi-hop relational structure, richer relational backbones, and more interpretable anomaly explanations.These directions would move beyond rules derived from flattened summaries and further leverage symbolic evidence.

GenAI Usage Disclosure

Generative AI tools assisted with code development and manuscript writing, while the authors reviewed the experimental design, implementation, results, analysis, and final manuscript decisions.

  • GenAI Usage Disclosure: Generative AI tools assisted with code development and manuscript writing.
  • GenAI Usage Disclosure: The authors reviewed all experimental design, implementation choices, results, analysis, and final manuscript decisions.
Loading 2608.23468v1…