Journal
IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE
Volume 31, Issue 3, Pages 563-569Publisher
IEEE COMPUTER SOC
DOI: 10.1109/TPAMI.2008.232
Keywords
Anomaly detection; co-occurrence analysis; unsupervised learning; variational methods; social networks
Funding
- US National Science Foundation [CCF-06-04397]
- US Defense Advanced Research Projects Agency [HT0011-07-1-003]
Ask authors/readers for more resources
This paper addresses the problem of detecting anomalous multivariate co-occurrences using a limited number of unlabeled training observations. A novel method based on using a hypergraph representation of the data is proposed to deal with this very high-dimensional problem. Hypergraphs constitute an important extension of graphs that allow 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 is 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, where n is the number of training observations and p is the number of potential participants in each co-occurrence event. This efficiency makes the method ideally suited for very high-dimensional settings and requires no tuning, bandwidth, or regularization parameters. The proposed approach is validated on both high-dimensional synthetic data and the Enron e-mail database, where p > 75,000, and it is shown that it can outperform other state-of-the-art methods.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available