An embedding scheme for detecting anomalous block structured graphs

Graph-based anomaly detection plays a vital role in various application domains such as network intrusion detection, social network analysis and road traffic monitoring. Although these evolving networks impose a curse of dimensionality on the learning models, they usually contain structural properties that anomaly detection schemes can exploit. The major challenge is finding a feature extraction technique that preserves graph structure while balancing the accuracy of the model against its scalability. We propose the use of a scalable technique known as random projection as a method for structure aware embedding, which extracts relational properties of the network, and present an analytical proof of this claim. We also analyze the effect of embedding on the accuracy of one-class support vector machines for anomaly detection on real and synthetic datasets. We demonstrate that the embedding can be effective in terms of scalability without detrimental influence on the accuracy of the learned model.