Ilmu Komputer & AI editorial
Open AccessOA2026
Not All Relations Are Equal: Relation-Balanced and Calibrated Graph Learning for Provenance-Based Intrusion Detection
RECAL: An Unsupervised Framework for Relation-Balanced Masked Graph Learning and Error Calibration in PIDSs
Lijie Zheng; Ji He; Zhiwei Zhang; Alessandro Brighente; Yulong Shen; Mauro Conti· 2026· DOI 10.48550/arXiv.2609.16462
The core problem
Provenance-Based Intrusion Detection Systems (PIDSs) are designed to detect Advanced Persistent Threats (APTs) by analyzing system-level interactions captured in provenance graphs. These graphs encode entities (e.g., processes, files, sockets) and their relations (e.g., read, write, execute). However, existing PIDSs largely treat all relations uniformly, ignoring the statistical heterogeneity inherent in real-world provenance data. For instance, in the CADETS dataset, relation frequencies differ by approximately , meaning some relations are extremely rare while others are overwhelmingly frequent. This imbalance can cause models to focus disproportionately on frequent relations, while overlooking rare but potentially malicious interaction patterns. Moreover, normal error levels vary across relations, leading to miscalibrated anomaly scores that increase both false alarms and missed detections. To address these challenges, the authors propose RECAL, an unsupervised framework that leverages relation-balanced masked graph learning and per-relation error calibration to produce comparable anomaly evidence across relations, thereby improving detection accuracy and reducin
Innovation
The authors evaluate RECAL on three DARPA E3 datasets: CADETS, THEIA, and TRACE. The performance is measured using score and False Positive Rate (FPR). RECAL achieves scores of 99.99%, 99.93%, and 99.99% on CADETS, THEIA, and TRACE, respectively. Compared to the best baseline on each dataset, RECAL improves by 0.88, 0.82, and 0.42 percentage points. More strikingly, in terms of FPR, RECAL reduces the mean FPR by approximately , , and relative to the baseline with the lowest FPR on each dataset. These results demonstrate that relation-balanced learning and calibration significantly enhance detection performance, particularly by minimizing false alarms while maintaining high detection rates.
Provenance-Based Intrusion Detection Systems (PIDSs) are designed to detect Advanced Persistent Threats (APTs) by analyzing system-level interactions captured in provenance graphs. These graphs encode entities (e.g., processes, files, sockets) and their relations (e.g., read, write, execute). However, existing PIDSs largely treat all relations uniformly, ignoring the statistical heterogeneity inherent in real-world provenance data. For instance, in the CADETS dataset, relation frequencies differ by approximately , meaning some relations are extremely rare while others are overwhelmingly frequent. This imbalance can cause models to focus disproportionately on frequent relations, while overlooking rare but potentially malicious interaction patterns. Moreover, normal error levels vary across relations, leading to miscalibrated anomaly scores that increase both false alarms and missed detections. To address these challenges, the authors propose RECAL, an unsupervised framework that leverages relation-balanced masked graph learning and per-relation error calibration to produce comparable anomaly evidence across relations, thereby improving detection accuracy and reducing false positives.
RECAL operates in two main stages: (1) relation-balanced masked graph learning and (2) per-relation error calibration.
Why it matters
The key insight of RECAL is that not all relations are equal: their frequencies and normal error distributions vary widely, and ignoring this heterogeneity leads to suboptimal detection. By balancing relation contributions during training, RECAL ensures that rare relations—often associated with stealthy attacks—are not overshadowed. The per-relation calibration further addresses the issue of incomparable reconstruction errors across relations, enabling a unified anomaly threshold. The substantial reduction in FPR is particularly important in operational settings, where false alarms can overwhelm security analysts. The unsupervised nature of RECAL also makes it practical for real-world deployment, as it does not require labeled attack data. However, the method assumes that benign error distributions can be reliably estimated from training data, which may be challenging in highly dynamic environments. Future work could explore adaptive calibration and extension to heterogeneous graph neural networks. Overall, RECAL sets a new benchmark for provenance-based intrusion detection by explicitly modeling relation-level statistics.
Who should read this
CS practitioners and researchers
Opening member content…