DGRMiner: Anomaly Detection and Explanation in Dynamic Graphs

This publication doesn't include Faculty of Arts. It includes Faculty of Informatics. Official publication website can be found on muni.cz.

Authors

VACULÍK Karel POPELÍNSKÝ Lubomír

Year of publication 2016
Type Article in Proceedings
Conference Advances in Intelligent Data Analysis XV - 15th International Symposium, IDA 2016
MU Faculty or unit

Faculty of Informatics

Citation
Doi http://dx.doi.org/10.1007/978-3-319-46349-0_27
Field Informatics
Keywords graph mining; data mining; dynamic graphs; rule mining; anomaly detection; outlier detection; anomaly explanation
Description Ubiquitous network data has given rise to diverse graph mining and analytical methods. One of the graph mining domains is anomaly detection in dynamic graphs, which can be employed for fraud detection, network intrusion detection, suspicious behaviour identification, etc. Most existing methods search for anomalies rather on the global level of the graphs. In this work, we propose a new anomaly detection and explanation algorithm for dynamic graphs. The algorithm searches for anomaly patterns in the form of predictive rules that enable us to examine the evolution of dynamic graphs on the level of subgraphs. Specifically, these patterns are able to capture addition and deletion of vertices and edges, and relabeling of vertices and edges. In addition, the algorithm outputs normal patterns that serve as an explanation for the anomaly patterns. The algorithm has been evaluated on two real-world datasets.
Related projects: