Statistical Detection of Network-Level Outliers

The search for anomalies or outliers in large-scale network data has important se-curity applications and can help to uncover interesting behavior. Four different types of anomalies can be discovered in static and dynamic network data: nodes, edges, small subgraphs, and/or larger (sub) networks. To date, most of the re-search in this area has focused on identifying anomalous nodes, links, or small subgraphs in static networks. In dynamic network data, research has focused on detecting outlier links and anomalous network evolution, where multiple, tempo-ral samples of the network provide sufficient data for analysis. However, to our knowledge, there are few algorithms that search for network-level anomalies in large-scale static networks. This is due to the difficulty of obtaining a set of net-works to use for learning statical models of normal behavior, coupled with model limitations that make it difficult to capture natural variations in the population. However, recent work on mixed Kronecker Product Graph Models (mKPGMs) has provided a statistical model that is capable of learning accurate models of net-work characteristics and network populations. Using this approach, we propose a novel outlier algorithm to detect anomalous networks in static network popula-tions, with a model-based approach that can learn the underlying distribution of the data from a single network. We illustrate the strengths of our algorithm using synthetic and real world network datasets, showing that the majority of outliers are detected using only a single network as training data.