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

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

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.