Tutorial: Outlier Detection for Graph Data

Outlier detection has been studied in the context of many research areas like statistics, data mining, sensor
networks, environmental science, distributed systems, spatio-temporal mining, etc. Outlier detection has
been studied on a large variety of data types including high-dimensional data, uncertain data, stream data,
graph data, time series data, spatial data, and spatio-temporal data. We present an organized picture of
recent research in outlier detection for graph data for both static as well as dynamic graphs. We begin by
motivating the importance of graph outlier detection and briefing the challenges beyond usual outlier detection.
Static graph outlier detection techniques include Minimum Description Length techniques, techniques
based on egonet metrics and random field models. For dynamic graphs, we discuss graph similarity based
algorithms, evolutionary community based algorithms and online graph outlier detection algorithms. We
also present applications where such techniques have been applied to discover interesting outliers.