# Not All Relations Are Equal: Relation-Balanced and Calibrated Graph Learning for Provenance-Based Intrusion Detection

arXiv: https://arxiv.org/abs/2609.16462 · HTML: https://mlsanity.com/paper/2609.16462/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 11 of its 23 references that are in the map.
- First posted on arXiv 15 Sep 2026.

## Builds on (most cited first, 11 of 11)

- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Efficient Estimation of Word Representations in Vector Space](https://mlsanity.com/paper/1301.3781/) (2013)
- [GraphMAE: Self-Supervised Masked Graph Autoencoders](https://mlsanity.com/paper/2205.10803/) (2022)
- [ECOD: Unsupervised Outlier Detection Using Empirical Cumulative Distribution Functions](https://mlsanity.com/paper/2201.00382/) (2022)
- [Relational Graph Attention Networks](https://mlsanity.com/paper/1904.05811/) (2019)
- [UNICORN: Runtime Provenance-Based Detector for Advanced Persistent Threats](https://mlsanity.com/paper/2001.01525/) (2020)
- [HOLMES: Real-time APT Detection through Correlation of Suspicious Information Flows](https://mlsanity.com/paper/1810.01594/) (2018)
- [Kairos: Practical Intrusion Detection and Investigation using Whole-system Provenance](https://mlsanity.com/paper/2308.05034/) (2023)
- [SLEUTH: Real-time Attack Scenario Reconstruction from COTS Audit Data](https://mlsanity.com/paper/1801.02062/) (2018)
- [threaTrace: Detecting and Tracing Host-based Threats in Node Level Through Provenance Graph Learning](https://mlsanity.com/paper/2111.04333/) (2021)
- [MAGIC: Detecting Advanced Persistent Threats via Masked Graph Representation Learning](https://mlsanity.com/paper/2310.09831/) (2023)

## Abstract (arXiv)

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×. 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×, 4×, and 41×.