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

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.