Anomaly detection in evolving (dynamic) graphs

Anomaly detection is an important task in data mining. Traditionally most of the anomaly detection algorithms have been designed for ‘static’ datasets, in which all the observations are available at one time. In non-stationary environments on the other hand, the same algorithms cannot be applied as the underlying data distributions change constantly and the same models are not valid. Hence, we need to devise adaptive models that take into account the dynamically changing characteristics of environments and detect anomalies in ‘evolving’ data. Over the last two decades, many algorithms have been proposed to detect anomalies in evolving data. Some of them consider scenarios where streaming objects with one or multiple features have causal/non-causal relationships with each other which can be represented as ‘dynamic graphs’. Although recently many studies on extending deep learning approaches for graph data have emerged, there is still a research gap on extending deep learning approaches for identifying anomalies in evolving graphs. In this research proposal, our aim is to explore the parallels of deep learning and anomaly detection in dynamic graphs. In particular we are interested to redesign deep neural networks so that they can accurately identify anomalies in the presence of concept drift. We would like to consider different types of changes in graph structures, such as emergence/deletion of new nodes/edges or the changes in the “normal” concept over time. Once we proposed relevant methods we intend to further extend the approach to be able to detect anomalies in high dimensional settings as the presence of irrelevant features can conceal the presence of anomalies. For this we propose to explore architectures such as deep belief networks (DBNs) as they are a promising technique for learning robust features.