New Approaches for Dynamic Graph Anomaly Detection, Prediction, and Explanation

异常检测是一个机器学习任务，它有许多实际的应用，如入侵检测，欺诈检测，医疗诊断，在制造过程中的缺陷检测，可疑行为检测等。这些真实世界的应用中的一些存在于一个动态的环境中，需要实时检测异常的数据流设置。检测、解释和预测异常（例如，可能的电网中断、病毒的快速传播等）是影响人们生活和组织决策的重要任务。我们的项目对社会的主要重大影响是：（i）提供准确的异常早期预警的新能力和（ii）以前无法提供的解释能力，为决策者和公众提供可靠的异常预警。异常的早期检测和预测使决策者和第一反应者有更多的时间来准备和克服异常的不利影响。我们项目的成功使需要规划和分配资源以及时处理异常情况的机构和地方政府受益。此外，解释清楚的异常现象会导致政府机构更好的缓解解决方案和资源分配，也会导致公众更好的个人决策。为此，每个利益相关者将受益于早期检测和预测，以及对异常的更清晰了解，以制定更好的应对即将发生的异常事件。 实时异常检测的应用越来越受到关注，这些应用涉及到诸如传感器网络、社交网络、计算机网络和电网之类的交互实体，这些实体可以使用演化图来建模。动态图异常检测的主要研究差距是，没有现有的框架，可以处理实时动态图异常检测，预测和解释任务在一个单一的系统。此外，缺乏理论来证明异常检测性能（即，假阳性率、延迟时间）。拟议的三年研究旨在：（i）设计用于假阳性控制的有效计算策略和通过用于动态图异常检测的多视图鞅决策过程的减少，（ii）设计用于使用真实的时间动态图异常预测的延迟时间减少的计算策略，（iii）探索一种新的由多视图决策过程和图中异常识别驱动的时间相关异常解释模型。该项目的长期目标是为复杂系统设计一个可靠有效的集成实时异常检测和解释框架。该奖项反映了NSF的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

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.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.