Abstract
The anomaly localization task aims at detecting faulty sensors automatically by monitoring sensor values. In this paper, we propose an anomaly localization algorithm with a consistency guarantee—meaning it is mathematically proven to correctly identify faulty sensors as the sample size increases. By framing the search for faulty sensors as a sparsest subgraph problem on a "difference graph" and solving it via a convex quadratic programming (QP) approximation, we provide a tool that is both computationally efficient and theoretically robust.
Introduction
In complex industrial systems, such as factories or vehicles, anomaly detection identifies if a failure has occurred, but anomaly localization is required to determine which specific sensors are malfunctioning. While various heuristic algorithms have been developed for this task over the last decade, they often lack theoretical guarantees of convergence. This research introduces the first anomaly localization method with a consistency guarantee: as the number of data samples grows, the algorithm is mathematically certain to identify the exact set of faulty sensors.
Methodology
The proposed approach represents sensor relationships using dependency graphs, such as Gaussian Graphical Models (GGMs). The localization process involves three primary stages:
- Difference Graph Construction: The algorithm computes the difference between the dependency graph of a "healthy" reference dataset and a "faulty" target dataset. In this difference graph, edges between healthy sensors should ideally have weights near zero, whereas edges involving faulty sensors exhibit higher weights.
- Sparsest Subgraph Formulation: The core insight is that healthy sensors form an independent set—a group of nodes with no edges between them—within the difference graph. Identifying these sensors is framed as finding the largest group of nodes that are disconnected from each other, known as the sparsest $k$-subgraph problem.
- Convex QP Approximation: Because the sparsest subgraph problem is NP-hard, the authors utilize a Convex Quadratic Programming (QP) relaxation. This approximation is solvable in polynomial time while maintaining the consistency guarantee, even when the number of healthy sensors ($k$) is unknown.
Experimental Evaluation
The method was evaluated using synthetic datasets (100 and 200 dimensions), real-world "Sun SPOT" accelerometer data from a vehicle, and motor current data from the UCR Time Series Archive involving 21 different operating conditions.
Key Results
- Theoretical Validation: Synthetic tests confirmed the consistency theorems, with the QP method achieving a perfect Area Under the Curve (AUC) of 1.0 as sample sizes increased.
- Performance Superiority: The QP method consistently outperformed existing state-of-the-art heuristics, which often plateaued at lower accuracy levels even with ample data.
- Real-World Robustness: The algorithm achieved the highest median AUC on noisy real-world datasets, demonstrating its practical utility for industrial applications.
- Computational Efficiency: The QP approximation proved computationally feasible for high-dimensional systems; for a 200-sensor network, the method processed data in seconds, making it suitable for real-time monitoring.
Conclusion and Future Work
This work transitions anomaly localization from heuristic-based tuning to a theoretically grounded science. By providing mathematical proof (Theorems 1-4), the authors ensure predictable outcomes for sensor maintenance. While the method is consistent, future research may focus on improving convergence rates through more sophisticated initial graph estimation techniques. Additionally, extending the framework from undirected graphs to directed causal graphs could enhance root-cause analysis in complex systems.
Summary updated