A simple graph embedding for anomaly detection in a stream of heterogeneous labeled graphs. (April 2021)

• Record Type: Journal Article
• Authors: Kiouche, Abd Errahmane; Lagraa, Sofiane; Amrouche, Karima; Seba, Hamida
• Is Part Of: Pattern recognition. Volume 112(2021)
• Publication Date: 2021-04
• Subjects: Graph anomaly detection -- Graph stream -- Graph embedding -- Graph edit distance; Pattern perception -- Periodicals; Perception des structures -- Périodiques; Patroonherkenning; 006.4
• DOI: 10.1016/j.patcog.2020.107746
• Languages: English
• ISSNs: 0031-3203

Abstract

Highlights: A new graph embedding is proposed for graph streams. A new incremental similarity measure based on graph edit distance Dealing with anomaly detection in a stream of heterogeneous labeled graphs. Allow the detection of anomalies in real-time. Graphical abstract: Abstract: In this work, we propose a new approach to detect anomalous graphs in a stream of directed and labeled heterogeneous edges. The stream consists of a sequence of edges derived from different graphs. Each of these dynamic graphs represents the evolution of a specific activity in a monitored system whose events are acquired in real-time. Our approach is based on graph clustering and uses a simple graph embedding based on substructures and graph edit distance. Our graph representation is flexible and updates incrementally the graph vectors as soon as a new edge arrives. This allows the detection of anomalies in real-time which is an important requirement for sensitive applications such as cyber-security. Our implementation results prove the effectiveness of our approach in terms of accuracy of detection and time processing.