Source-linked AI summary
Not All Relations Are Equal: Relation-Balanced and Calibrated Graph Learning for Provenance-Based Intrusion Detection
Lijie Zheng, Ji He, Alessandro Brighente, Yulong Shen, Mauro Conti
TL;DR
Existing PIDSs treat heterogeneous relations uniformly, despite large frequency differences and relation-specific benign error scales. RECAL combines relation-balanced masked graph learning with calibrated reconstruction-error evidence, achieving the highest F1 and low false positive rates across three DARPA E3 scenarios. Its deviation-based detection remains limited when attack-associated entities closely resemble benign local behavior.
Problem
Existing PIDSs largely treat relations uniformly despite heterogeneous frequencies and normal error scales, creating capacity misallocation and cross-relation score miscalibration.
Method
RECAL combines relation-balanced masked graph learning with relation-calibrated anomaly detection using relation-specific reconstruction errors and benign error distributions.
Results
Across CADETS, THEIA, and TRACE, RECAL achieves the highest F1 among compared methods—99.99%, 99.93%, and 99.99%—while maintaining mean FPRs of 0.0004%, 0.0041%, and 0.0019%, respectively.
Takeaways & Limitations
Relation-balanced learning and calibrated evidence help control false alarms while preserving high F1 across the three evaluated DARPA E3 scenarios.
Takeaways & Limitations
Deviation-based detection can miss attack-associated entities whose local interaction patterns substantially overlap benign behavior.
Abstract
from arXiv · showhide
Provenance-Based Intrusion Detection Systems (PIDSs) detect Advanced Persistent Threats (APTs) by analyzing system interactions. However, existing methods largely treat relations uniformly, overlooking statistical heterogeneity; in CADETS, relation frequencies differ by approximately $140{,}000\times$. This may cause PIDSs to focus more on frequent relations and overlook differences in normal error levels across relations, increasing the risk of false alarms and missed detections. We present RECAL, an unsupervised framework using relation-balanced masked graph learning to better capture rare interaction patterns. It further calibrates reconstruction errors against each relation's benign error distribution to produce comparable anomaly evidence, helping distinguish attacks from benign behavior and reduce false alarms. On three DARPA E3 datasets, RECAL achieves F1 scores of 99.99\%, 99.93\%, and 99.99\%, outperforming the best baseline on each dataset by 0.88, 0.82, and 0.42 percentage points, respectively. Compared with the baseline reporting the lowest FPR, RECAL reduces mean FPR by approximately $105\times$, $4\times$, and $41\times$.
1. INTRODUCTION
Existing PIDSs overlook severe relation heterogeneity, allowing frequent interactions to dominate learning and making anomaly scores difficult to compare across relations. RECAL addresses these issues with relation-balanced masked graph learning and relation-calibrated detection, achieving strong results across three DARPA E3 datasets.
- 1. INTRODUCTION: 140,000× separates CADETS relation event counts, yet existing PIDSs treat relations uniformly, creating capacity misallocation and cross-relation score miscalibration.Frequent relations can dominate learning, while a global threshold may over-alert on some relations and overlook anomalies on others.
- 1. INTRODUCTION: RECAL integrates relation-balanced masked graph learning with relation-calibrated detection to model frequent and rare interactions while reducing false alarms.Its design combines balanced learning with calibrated anomaly evidence across relations.
- 1. INTRODUCTION: RECAL’s relation-stratified masking, independent decoder heads, balanced reconstruction, quantile calibration, and Fisher fusion address frequent-relation dominance and align cross-relation evidence.The framework is unsupervised and produces comparable anomaly evidence from relation-specific reconstruction errors.
- 1. INTRODUCTION: Across three DARPA E3 datasets, RECAL achieves the highest F1 among compared methods while maintaining lower false positive rates.The introduction reports systematic evaluation on three datasets, with implementation made available for further use.
2. METHODOLOGY
RECAL converts audit logs into typed provenance graphs, learns relation-balanced masked representations, and calibrates relation-specific reconstruction errors for two-stage anomaly detection. Its pipeline combines rare-relation modeling, KNN candidate screening, within-relation quantile calibration, and Fisher evidence fusion.
- Pipeline overview: RECAL converts kernel audit logs into directed heterogeneous provenance graphs, then uses node embeddings for KNN screening and relation-specific errors for calibrated evidence fusion.The pipeline includes graph construction, node featurization, relation-balanced masked graph learning, and relation-calibrated detection.
- Node featurization: Temporal relation-transition profiles augment node features with short-range behavioral context, making patterns such as receive→write→execute visible without training.Each node feature combines entity type, semantic embedding, and a temporal transition profile with decay.
- Relation-Balanced Masked Graph Learning: Relation-balanced masking assigns frequency-dependent masking rates, increasing reconstruction opportunities for rare relations while bounding each relation’s sampling probability.The exponent γ controls rare-relation emphasis, and selected nodes receive a learnable mask vector.
- Relation-Balanced Masked Graph Learning: Independent relation-specific decoders and equal weighting of nonempty per-relation mean losses model distinct interaction patterns without letting sample counts dominate optimization.Per-relation reconstruction errors are retained for later comparison against relation-specific benign baselines.
- Relation-Calibrated Anomaly Detection: Relation calibration maps candidate reconstruction errors to within-relation benign quantiles, placing deviations from different relations on a common comparison scale.The benign period’s tail is held out to estimate relation-specific empirical CDFs after model training.
- Relation-Calibrated Anomaly Detection: Fisher’s method fuses upper-tail evidence across each candidate’s participating relations, using an approximate χ2 reference and thresholding the resulting score for alarms.The method accounts for the number of participating relations, while subsequent calibration and fusion require only table lookups and χ2 CDF evaluations.
3. EXPERIMENTS
RECAL achieves strong detection performance across three DARPA E3 scenarios, while ablations, sensitivity tests, and runtime analysis examine its components, robustness, and cost.
- 3.2. Main Results: 99.99%, 99.93%, and 99.99% F1 are the highest scores among compared methods on CADETS, THEIA, and TRACE, respectively.RECAL also reports mean FPRs of 0.0004%, 0.0041%, and 0.0019% on the three scenarios.
- 3.2. Main Results: Approximately 105×, 4×, and 41× mean-FPR reductions are achieved versus STGAN on CADETS, THEIA, and TRACE, respectively.STGAN is identified as the baseline with the lowest reported FPRs in the comparison table.
- 3.2. Main Results: Eighteen THEIA nodes remain undetected because their local interaction patterns substantially overlap with benign behavior.Although these nodes enter the candidate set, their calibrated and fused evidence remains below the final detection threshold.
- 3.3. Ablation Study: Removing relation-calibrated detection reduces mean F1 by 3.94, 0.50, and 0.48 percentage points on CADETS, THEIA, and TRACE, respectively.The joint uniform-masking/shared-decoder variant has lower mean F1 on CADETS and TRACE, slightly higher mean F1 on THEIA, and higher mean FPRs across all scenarios.
- 3.3. Ablation Study: Calibration separates benign and malicious node scores more clearly, while z-score calibration and maximum or mean aggregation reduce F1 and increase FPR.On CADETS, z-score calibration raises mean FPR to 0.2261%; Fisher’s method accumulates evidence across relations.
- 3.4. Parameter Sensitivity: F1 remains above 99.5% with only 1% of reserved calibration nodes, and varies by less than 0.01 percentage points between 5 and 20 masking rounds.Increasing masking rounds raises forward-pass cost, while γ = 0.5 gives the highest F1 and lowest FPR on CADETS and THEIA.
- 3.5. Computational Efficiency: KNN construction and queries account for 98.9% of inference time on TRACE, whereas calibration and Fisher fusion take approximately 0.5% to 2.1%.Training takes about 217 seconds and inference over approximately 3.3 million TRACE nodes takes about 284 seconds.
4. CONCLUSION
RECAL performs unsupervised provenance-based intrusion detection using relation-balanced masked graph learning and relation-calibrated anomaly detection. Across three DARPA E3 scenarios, it achieves the highest F1 among compared methods while maintaining low false positive rates.
- RECAL achieves the highest F1 among compared methods across three DARPA E3 scenarios while maintaining low false positive rates.
- RECAL combines relation-balanced masked graph learning with relation-calibrated anomaly detection for unsupervised provenance-based intrusion detection.
- Future work will explore adaptive relation calibration to address concept drift in long-running deployments.
5. COMPLIANCE WITH ETHICAL STANDARDS
The study uses publicly available DARPA E3 system-audit datasets and involves no human or animal subjects. Therefore, no ethical approval was required.
- The study uses publicly available DARPA E3 system-audit datasets and involves no human or animal subjects.
- No ethical approval was required.