TL;DR
This paper introduces DeepSphere, a novel framework for discovering anomalies in dynamic networks. It tackles the challenge of identifying both overall system anomalies and pinpointing specific anomalous components within them, all without requiring labeled data. DeepSphere combines deep autoencoders with hypersphere learning to achieve robust and transparent anomaly detection.
What Problem Does This Paper Address?
Intelligent networked systems, from transportation to cloud computing, are becoming increasingly complex and dynamic. Understanding their "normal" behavior and automatically identifying "abnormal" situations is crucial for maintaining stability and enabling timely interventions. Existing methods often struggle with one or both of these requirements: some can detect system-level anomalies but lack transparency into the root causes, while others can identify localized issues but fail to provide an overall system warning. Furthermore, many approaches require clean, anomaly-free training data, which is often unrealistic in real-world scenarios where data can be "polluted" with anomalies. This paper addresses the need for a unified, unsupervised approach that can detect both case-level anomalies (entire system states) and nested anomalies (specific components within a system) while providing transparency and robustness to imperfect training data.
Methods
DeepSphere is a unified, end-to-end framework that integrates two key components:
- Deep Autoencoder (specifically LSTM Autoencoder): This part of the architecture learns a compressed, low-dimensional representation of the input data. By using LSTMs, it's particularly adept at capturing temporal dependencies and structural relationships within dynamic network data (represented as tensors). The autoencoder's goal is to reconstruct the input data from its compressed representation.
- Hypersphere Learning: This novel component is integrated as a specialized layer. It learns a compact spherical boundary around the representations of "normal" data points in the latent space. This boundary serves two purposes:
- Anomaly Pollution Exclusion: It helps to isolate and penalize anomalous data points that fall outside the hypersphere during training, thus improving the quality of the autoencoder's learned representations.
- Case-Level Anomaly Scoring: The distance of a new data point to the hypersphere's centroid is used as an anomaly score, indicating the likelihood of the entire case being anomalous.
The framework combines these by using the hypersphere's output to weight the reconstruction error of the autoencoder. This "weighted reconstruction error" ensures that data points far from the hypersphere (anomalous) contribute less to the reconstruction, while those closer (normal) contribute more. The overall objective function is a combination of the hypersphere learning objective and this weighted reconstruction error.
Datasets
The paper evaluates DeepSphere on both synthetic and real-world datasets:
- Synthetic Data: Generated to comprehensively test performance under various conditions, including:
- Anomaly pollution levels in training data.
- Spatio-temporal locality of anomalies.
- Extent of nested anomalies.
- Data imbalance in testing data.
- Real-World Data:
- NYC Taxi Trips: Public transportation data used to construct temporal graphs of taxi movements, detecting anomalous transportation phenomena.
- Tweets & News Collection (HERMEVENT): A semantic dataset used to build temporal graphs of phrase co-occurrences, identifying news events.
- Restaurant Video: Frames from a restaurant video used to detect foreground activities, demonstrating applicability beyond graph data.
Key Insights and Ideas
- Unified Two-Level Anomaly Discovery: The paper formalizes a critical problem: simultaneously detecting system-level anomalies and revealing their internal structure. This is a significant step beyond methods that only address one aspect.
- Hypersphere for Robustness: Integrating hypersphere learning is key to handling "anomaly pollution" in training data. This makes the model more practical for real-world scenarios where perfectly clean data is rare.
- Inductive Learning: The model is designed to generalize to unseen test data, a crucial requirement for real-time anomaly detection systems.
- Transparency through Nested Anomaly Discovery: Beyond just flagging an anomaly, DeepSphere aims to show where and how the anomaly manifests within the system, aiding in diagnosis and intervention.
- Broad Applicability: The successful application to diverse datasets (graphs, text-derived graphs, video) suggests the framework's potential for various dynamic systems.
Key Results
- Superior Performance: DeepSphere consistently outperformed baseline methods (RAE, LSTM-AE, TSHL, LOF, OC-SVM) on both case-level anomaly detection (measured by Kappa statistics) and nested anomaly discovery (measured by RMSE) across various synthetic scenarios.
- Robustness: The model showed stable performance even with increasing anomaly pollution, varying spatio-temporal locality, and data imbalance.
- Case-Level Detection: DeepSphere and TSHL (both using hypersphere learning) performed best in case-level detection, highlighting the benefit of this technique for handling anomaly pollution.
- Nested Anomaly Discovery: DeepSphere achieved the lowest RMSE for nested anomaly discovery, outperforming other deep learning models.
- Real-World Validation: The paper demonstrated DeepSphere's ability to uncover meaningful anomalies in real-world taxi trip data, news events, and restaurant video activity.
Limitations and Future Work
- Limitations:
- The paper acknowledges that fully capturing nested anomalies becomes more challenging as their size and complexity increase.
- Performance can decline with significant data imbalance in test sets.
- Future Work:
- Extend the framework to exploit multiple data sources for richer anomaly detection.
- Explore the problem of anomaly source detection within networks, going beyond just identifying anomalies to pinpointing their origin.
Summary updated