MASA: An efficient framework for anomaly detection in multi-attributed networks

Anomalous connected subgraph detection has been widely used in multiple scenarios, such as botnet detection, fraud detection and event detection. Nevertheless, the huge search space makes a serious computational challenge. Moreover, the anomalous connected sub graph detection becomes much harder when the networks involve a large number of attributes and become the multi-attributed networks. With the multi-attributed characteristic, most existing approaches are unable to solve this problem effectively and efficiently since it involves the anomalous connected subgraph detection and attributes selection simultaneously. In view of this, this paper proposes a general framework, namely multi attributed anomalous subgraphs and attributes scanning (MASA), to solve this problem in multi-attributed networks. We formulate and optimize a great number of complicated non parametric scan statistic functions that are employed to measure the joint anomalousness of the connected subgraphs and the corresponding subset of attributes in multi-attributed networks. More specifically, we first propose to transform each formulated nonparametric scan statistic function into a set of sub-functions with the theoretical analysis. Then using techniques of the tree approximation priors and the dynamic algorithms, an efficient approximation algorithm is presented to solve each transformed sub-function. Finally, with three real-world datasets from different domains, we conduct extensive experimental evaluations to demonstrate the effectiveness and efficiency of the proposed approach. (c) 2020 Elsevier Ltd. All rights reserved.

Automated summary

This research proposes a general framework named MASA to solve the problem of anomalous connected subgraph detection in multi-attributed networks. By formulating and optimizing complex nonparametric scan statistic functions, the joint anomalousness of connected subgraphs and attributes subset in multi-attributed networks is measured, and an efficient approximation algorithm is presented. Extensive experimental evaluations on real-world datasets demonstrate the effectiveness and efficiency of the proposed approach.