A Consistent Method for Graph Based Anomaly Localization

Satoshi Hara, Tetsuro Morimura, Toshihiro Takahashi, Hiroki Yanagisawa, Taiji Suzuki
Proceedings of the Eighteenth International Conference on Artificial Intelligence and Statistics, PMLR 38:333-341, 2015.

Abstract

The anomaly localization task aims at detecting faulty sensors automatically by monitoring the sensor values. In this paper, we propose an anomaly localization algorithm with a consistency guarantee on its results. Although several algorithms were proposed in the last decade, the consistency of the localization results was not discussed in the literature. To the best of our knowledge, this is the first study that provides theoretical guarantees for the localization results. Our new approach is to formulate the task as solving the sparsest subgraph problem on a difference graph. Since this problem is NP-hard, we then use a convex quadratic programming approximation algorithm, which is guaranteed to be consistent under suitable conditions. Across the simulations on both synthetic and real world datasets, we verify that the proposed method achieves higher anomaly localization performance compared to existing methods.

Cite this Paper

BibTeX
@InProceedings{pmlr-v38-hara15, title = {{A Consistent Method for Graph Based Anomaly Localization}}, author = {Hara, Satoshi and Morimura, Tetsuro and Takahashi, Toshihiro and Yanagisawa, Hiroki and Suzuki, Taiji}, booktitle = {Proceedings of the Eighteenth International Conference on Artificial Intelligence and Statistics}, pages = {333--341}, year = {2015}, editor = {Lebanon, Guy and Vishwanathan, S. V. N.}, volume = {38}, series = {Proceedings of Machine Learning Research}, address = {San Diego, California, USA}, month = {09--12 May}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v38/hara15.pdf}, url = {https://proceedings.mlr.press/v38/hara15.html}, abstract = {The anomaly localization task aims at detecting faulty sensors automatically by monitoring the sensor values. In this paper, we propose an anomaly localization algorithm with a consistency guarantee on its results. Although several algorithms were proposed in the last decade, the consistency of the localization results was not discussed in the literature. To the best of our knowledge, this is the first study that provides theoretical guarantees for the localization results. Our new approach is to formulate the task as solving the sparsest subgraph problem on a difference graph. Since this problem is NP-hard, we then use a convex quadratic programming approximation algorithm, which is guaranteed to be consistent under suitable conditions. Across the simulations on both synthetic and real world datasets, we verify that the proposed method achieves higher anomaly localization performance compared to existing methods.} }
Endnote
%0 Conference Paper %T A Consistent Method for Graph Based Anomaly Localization %A Satoshi Hara %A Tetsuro Morimura %A Toshihiro Takahashi %A Hiroki Yanagisawa %A Taiji Suzuki %B Proceedings of the Eighteenth International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2015 %E Guy Lebanon %E S. V. N. Vishwanathan %F pmlr-v38-hara15 %I PMLR %P 333--341 %U https://proceedings.mlr.press/v38/hara15.html %V 38 %X The anomaly localization task aims at detecting faulty sensors automatically by monitoring the sensor values. In this paper, we propose an anomaly localization algorithm with a consistency guarantee on its results. Although several algorithms were proposed in the last decade, the consistency of the localization results was not discussed in the literature. To the best of our knowledge, this is the first study that provides theoretical guarantees for the localization results. Our new approach is to formulate the task as solving the sparsest subgraph problem on a difference graph. Since this problem is NP-hard, we then use a convex quadratic programming approximation algorithm, which is guaranteed to be consistent under suitable conditions. Across the simulations on both synthetic and real world datasets, we verify that the proposed method achieves higher anomaly localization performance compared to existing methods.
RIS
TY - CPAPER TI - A Consistent Method for Graph Based Anomaly Localization AU - Satoshi Hara AU - Tetsuro Morimura AU - Toshihiro Takahashi AU - Hiroki Yanagisawa AU - Taiji Suzuki BT - Proceedings of the Eighteenth International Conference on Artificial Intelligence and Statistics DA - 2015/02/21 ED - Guy Lebanon ED - S. V. N. Vishwanathan ID - pmlr-v38-hara15 PB - PMLR DP - Proceedings of Machine Learning Research VL - 38 SP - 333 EP - 341 L1 - http://proceedings.mlr.press/v38/hara15.pdf UR - https://proceedings.mlr.press/v38/hara15.html AB - The anomaly localization task aims at detecting faulty sensors automatically by monitoring the sensor values. In this paper, we propose an anomaly localization algorithm with a consistency guarantee on its results. Although several algorithms were proposed in the last decade, the consistency of the localization results was not discussed in the literature. To the best of our knowledge, this is the first study that provides theoretical guarantees for the localization results. Our new approach is to formulate the task as solving the sparsest subgraph problem on a difference graph. Since this problem is NP-hard, we then use a convex quadratic programming approximation algorithm, which is guaranteed to be consistent under suitable conditions. Across the simulations on both synthetic and real world datasets, we verify that the proposed method achieves higher anomaly localization performance compared to existing methods. ER -
APA
Hara, S., Morimura, T., Takahashi, T., Yanagisawa, H. & Suzuki, T.. (2015). A Consistent Method for Graph Based Anomaly Localization. Proceedings of the Eighteenth International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 38:333-341 Available from https://proceedings.mlr.press/v38/hara15.html.

Related Material