A Comprehensive Review on Graph-Based Anomaly Detection: Approaches for Intrusion Detection

Intrusion Detection Systems (IDSs) have evolved to safeguard networks and systems from cyber attacks. Anomaly-based Intrusion Detection Systems (A-IDS) have been commonly employed to detect known and unknown anomalies. However, conventional anomaly detection approaches encounter substantial challenges when dealing with large-scale and heterogeneous data sources. These challenges include high False Positive Rates (FPRs), imbalanced data behavior, complex data handling, resource constraints, limited interpretability, and difficulties with encrypted networks. This survey reviews 60 technical papers (2019–2025) on graph-based anomaly detection (GBAD) approaches, highlighting their ability to address these challenges by utilizing the inherent structure of graphs to capture and analyze network connectivity patterns. Our analysis reveals that 32 studies (53%) employ two-stage methods while 28 (47%) use end-to-end approaches. Among the end-to-end methods, GNN-based techniques dominate, accounting for 18 of the 28 papers. We present a phased graph-based anomaly detection methodology for intrusion detection. This includes phases of data capturing, graph construction, graph pre-processing, anomaly detection, and post-detection analysis. Furthermore, we examine the evaluation methods and datasets employed in GBAD research and provide an analysis of the types of attacks identified by these methods. The most utilized datasets include CICIDS, UNSW-NB15, and DARPA, while precision, recall, and F1-score are employed in over 85% of studies. Lastly, we outline the key challenges and future directions that require significant research efforts in this area, and we offer some recommendations to address them.