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

异常检测是一项机器学习任务，在入侵检测、欺诈检测、医疗诊断、制造过程缺陷检测、可疑行为检测等方面有着广泛的应用。其中一些实际应用存在于动态环境中，需要实时检测数据流设置中的异常。检测、解释和预测异常情况（例如，电网可能中断、病毒迅速传播等）是影响人们生活和组织决策的重要任务。我们的项目对社会的主要影响是：(i)为异常提供准确的早期预警的新能力；（ii）以前不可用的解释能力，为决策者和公众提供可靠的异常预警。早期发现和预测异常可以让决策者和急救人员有更多的时间来准备和克服异常的不利影响。我们项目的成功使需要规划和分配资源以及时处理异常情况的机构和地方政府受益。此外，对异常现象的充分解释可以使政府机构采取更好的缓解办法和资源分配，也可以使公众作出更好的个人决定。为此，每个利益相关者都将受益于早期发现和预测以及对异常的更清晰理解，从而更好地应对即将发生的异常事件。人们对实时异常检测应用越来越感兴趣，这些应用涉及可使用演化图建模的交互实体，如传感器网络、社交网络、计算机网络和电网。动态图异常检测的主要研究缺口是目前还没有能够在单个系统内处理实时动态图异常检测、预测和解释任务的框架。此外，缺乏理论来证明现有方法的异常检测性能（即误报率，延迟时间）。本课题为期三年的研究目标是：(1)设计一种基于动态图异常检测的多视图鞅决策过程控制和减少误报的有效计算策略；(2)设计一种基于实时动态图异常预测的延迟时间减少计算策略；(3)探索一种基于多视图决策过程驱动的与图异常识别相关的新的时间依赖性异常解释模型。本课题的长期目标是为复杂系统设计一个可靠有效的综合实时异常检测与解释框架。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

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.