Dynamic Graph Anomaly Detection

Award Abstract # 2213658 - New Approaches for Dynamic Graph Anomaly Detection, Prediction, and Explanation

Start Date: September 1, 2022

End Date: August 31, 2025 (Estimated)

PI: Dr. Shen-Shyang Ho

Abstract:

Anomaly detection is a machine learning task which has many practical applications such as intrusion detection, fraud detection, medical diagnosis, defect detection during manufacturing process, suspicious behavior detection, etc. Some of these real-world applications exist in a dynamic environment which require real-time detection of anomalies in a data streaming setting. Detecting, explaining and predicting anomalies (e.g., likely outages in a power grid, rapid spread of virus, etc.) are important tasks that affect the life of people and organizational decision making. The main significant impacts of our project to society are: (i) new capabilities to provide accurate early warnings for anomalies and (ii) previously unavailable explanation capability to provide trustworthy warnings of anomaly to decision makers and general public. Early detection and prediction of anomalies allow decision makers and first responders more time to prepare and overcome the anomalies' adverse effects. The success of our project benefits agencies and local governments that require the planning and allocation of resources to handle anomalies in a timely manner. Moreover, well explained anomaly leads to better mitigation solutions and resource allocation by government agencies and also better individual decision by the general public. Towards this end, every stakeholder will benefit from early detection and prediction together with a clearer understanding of the anomaly to develop better responses to the imminent abnormal event.

There is growing interest in real-time anomaly detection applications involving interacting entities such as sensor network, social network, computer network, and power grid that can be modeled using evolving graphs. The major research gap in dynamic graph anomaly detection is that there is no existing framework that can handle real-time dynamic graph anomaly detection, prediction, and explanation tasks within a single system. Moreover, there is a lack of theory to justify anomaly detection performance (i.e., false positive rate, delay time) for existing methods. The proposed three-year research aims to: (i) design an effective computational strategy for false positive control and reduction by multi-view martingale decision process for dynamic graph anomaly detection, (ii) design a computational strategy for delay time reduction using real time dynamic graph anomaly prediction, and (iii) explore a new time-dependent anomaly explanation model driven by the multi-view decision process together with anomaly identification in graph. The long-term objective of this project is to design a reliable and effective integrated real-time anomaly detection and explanation framework for a complex system.

Participating Undergraduate/Graduate Students:

1. Izhar Ali (July 2024 - May 2025) - MSDS (Thesis)

Former Students:

1. Chinmai Reddy Modugula (March 2023 - December) - MSDS

2. Tarun Teja Kairamkonda (January 2023 - May 2024) - MSCS (Thesis)

3. Mahender Rao, Samperboyina, (November 2023 - December 2024) - MSCS

Publications:

1. Shen-Shyang Ho, Tarun Teja Kairamkonda, and Izhar Ali, Detecting and Explaining Structural Changes in an Evolving Graph using a Martingale, Pattern Recognition (accepted)

2. Shen-Shyang Ho and Tarun Teja Kairamkonda, Change Point Detection in Evolving Graph using Martingale, 39th ACM/SIGAPP Symposium On Applied Computing, Avila, Spain, April 8 - April 12, 2024

3. Tarun Teja Kairamkonda, AN EMPIRICAL STUDY ON DETECTING AND EXPLAINING GLOBAL STRUCTURAL CHANGE IN EVOLVING GRAPH USING MARTINGALE (MSCS Thesis, 2024)

Articles:

https://today.rowan.edu/news/2022/12/machine-learning-could-help-predict-defects-fraud-cancer.html

===

This material is based upon work supported by the National Science Foundation under Grant Number 2213658.

Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation.