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

动态图异常检测、预测和解释的新方法

• 批准号: 2213658
• 负责人: Shen Shyang Ho
• 金额: $ 27.3万
• 依托单位: Rowan University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2022
• 资助国家: 美国
• 起止时间: 2022-09-01 至 2025-08-31
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2213658&HistoricalAwards=false
• 关键词: New; Approaches; Dynamic; Graph; Anomaly

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.

异常检测是一种机器学习任务，在入侵检测、欺诈检测、医疗诊断、制造过程缺陷检测、可疑行为检测等方面有着广泛的应用。检测、解释和预测异常(例如，电网中可能的停电、病毒的快速传播等)是影响人们生活和组织决策的重要任务。我们的项目对社会的主要重大影响是：(I)提供准确的异常早期警告的新能力，以及(Ii)向决策者和普通公众提供可靠的异常警告的以前无法解释的能力。及早发现和预测异常，使决策者和第一反应人员有更多时间准备和克服异常的不利影响。我们项目的成功使需要规划和分配资源以及时处理异常情况的机构和地方政府受益。此外，经过充分解释的异常情况会导致政府机构更好的缓解方案和资源分配，也会让公众做出更好的个人决定。为此，每个利益攸关方都将受益于及早发现和预测，以及更清楚地了解异常情况，以便对即将发生的异常事件做出更好的反应。人们对涉及诸如传感器网络、社交网络、计算机网络和电网之类的交互实体的实时异常检测应用越来越感兴趣，这些实体可以使用演化图来建模。动态图异常检测的主要研究空白是没有现有的框架可以在单个系统内处理实时动态图异常检测、预测和解释任务。此外，现有方法的异常检测性能(即误检率、延迟时间)缺乏理论依据。这项为期三年的研究旨在：(I)设计一种有效的用于动态图异常检测的多视点鞅决策过程来控制和减少误报的计算策略；(Ii)设计一种利用实时动态图异常预测来减少延迟时间的计算策略；(Iii)探索一种由多视点决策过程和图中的异常识别驱动的新的时间相关异常解释模型。该项目的长期目标是为复杂系统设计可靠有效的集成实时异常检测和解释框架。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。