Collaborative Research: OAC Core: Fast Tools for Complex Event Detection over Bipartite Graph Streams

该项目的目标是设计有效和可扩展的方法和软件基础设施来检测二部图流中的复杂事件。二部图被广泛应用于各种领域，以模拟现实世界的关系，如信用卡交易、网络搜索和数据挖掘、计算广告、生物信息学和大众分类法。在处理二部图流时，包括组合爆炸在内，存在着重大的计算挑战。二部图流中的主题和复杂事件检测和计数有许多用例，包括在线购物服务和个性化音乐/电影流媒体平台中的推荐系统，以及信用卡交易、产品评级数据（即垃圾邮件评论）、客户端/服务器网络交互、社会保障和医疗保健系统（例如可疑破产申报和税务欺诈）中的恶意活动检测。该项目将开发有效的工具和软件基础设施，以促进这些领域的研究和发展。通过基础设施，包括计算机科学家、商业研究人员和经济学家、社会科学家和网络安全工程师在内的各个学科的研究人员和实践者将能够访问和共享数据集，并使用和贡献工具库和文档。二部图流中的复杂事件通常不能仅通过孤立地查看单个节点/边缘到达来检测。相反，检测需要在一段时间内监视流。该项目有三个主要任务：(1)将基序视为基本复杂事件或较大复杂事件中的组成部分，该项目将开发动态和流算法，用于二部图流中的组合和时间基序检测和计数；(2)开发了部分时间阶复杂事件和密集子图事件的检测方法；(3)为复杂事件设计图嵌入方法，指定二部图流中实体之间的高阶相似性，并为能够找到并包含缺失边的预测性复杂事件设计图嵌入方法。该项目将通过结构分析、基序分析和二部图的神经嵌入的流和增量算法，为图算法和机器学习的知识体系做出贡献。该项目将在目前用于静态二部图的批量分析和流式二部图的增量和时间分析的方法之间建立平行关系。这项工作将为复杂事件检测领域提供基础方法。这些工具和软件基础设施将促进计算机科学、社会科学、金融和商业以及网络安全领域的研究人员和从业人员方便地访问和共享数据集、最先进的方法和工具、文档和评估结果。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

The goal of the project is to devise efficient and scalable methods and software infrastructure for detecting complex events in bipartite graph streams. Bipartite graphs are widely used in various domains to model real-world relationships such as credit card transactions, web search and data mining, computational advertising, bioinformatics, and folksonomy. There are significant computational challenges in handling bipartite graph streams including combinatorial explosion. Motifs and complex event detection and counting in bipartite graph streams have many use cases including recommendation systems in online shopping services and personalized music/movie streaming platforms, as well as malicious activity detection in credit card transactions, product rating data (i.e., spam reviews), client/server network interactions, and social security and healthcare systems (e.g., suspicious bankrupt declarations and tax fraud). The project will develop efficient tools and software infrastructure to facilitate research and development in these areas. Through the infrastructure, researchers and practitioners in various disciplines including computer scientists, business researchers and economists, social scientists, and network security engineers will be able to access and share datasets, and to use as well as contribute to the tool repository and documentation.Complex events in a bipartite graph stream typically cannot be detected by only looking at a single node/edge arrival in isolation. Instead, detection requires monitoring the stream over a period of time. The project has three main tasks: (1) considering motifs as basic complex events or components in a larger complex event, the project will develop dynamic and streaming algorithms for combinatorial and temporal motif detection and counting in bipartite graph streams; (2) developing methods for detecting complex events with a partial time order, as well as dense-subgraph events; (3) devising graph embedding methods for complex events that specify high-order similarity between entities in a bipartite graph stream and for predictive complex events that can find and include the missing edges. The project will contribute to the body of knowledge about graph algorithms and machine learning through streaming and incremental algorithms for structural analysis, motif analysis, and neural embedding of bipartite graphs. The project will draw a parallel between the methods currently applied for batch analysis of static bipartite graphs and incremental and temporal analysis of streaming bipartite graphs. This work will provide foundational methods for the area of complex event detection. The tools and software infrastructure will facilitate researchers and practitioners in computer science, social sciences, finance and business, and network security to conveniently access and share datasets, state-of-the-art methods and tools, documentation, and evaluation results.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.