When monitoring interactions within a network, co-occurrence data can often represent critical information, such as routers in different packet routes or collections of links being traversed at different times. In this talk, I will discuss the problem of detecting anomalous network co-occurrences using a limited number of unlabeled training observations. In particular, I will consider n recorded co-occurrences among p potential participants (e.g. routers or links), where both n and p may be very large. I will describe a novel method based on a hypergraph representation of the data to deal with this very high- dimensional, “big-p-small-n” problem. Hypergraphs are an important extension of graphs, allowing edges to connect more than two vertices simultaneously. A variational Expectation-Maximization algorithm for detecting anomalies directly on the hypergraph domain without any feature selection or dimensionality reduction will be presented. The resulting estimate can be used to calculate a measure of anomalousness based on the False Discovery Rate. The algorithm has O(np) computational complexity, making it ideally suited for very high- dimensional settings, and requires no tuning, bandwidth or regularization parameters.
Copyright. All Rights Reserved.