EAGER: Multi-Stream Graph Mining

Washington State University, Pullman WA

Investigators

Abstract

Graphs, or networks of nodes and links, have proven to be effective for discovering patterns in many applications where data are generated from multiple and connected sources. In complex real-world applications, graphs are typically collected over time, known as graph stream data. Existing graph-based approaches for knowledge discovery are computationally challenging, particularly when analyzing large amounts of graph streams. In addition, a better understanding of intrinsic patterns typically cannot be obtained through mining a single graph stream. This project aims to investigate a new approach capable of scalable knowledge discovery in multiple graph streams, called multi-stream graph mining. The approach is novel and potentially transformative in how knowledge is discovered from multiple data streams. The project will have significant impact by providing efficient and effective tools for detecting patterns in heterogeneous data that can lead to new discoveries in a variety of domains where large amounts of dynamic data are available, including cyber-security and social media. This project will investigate a group of data mining approaches for mining patterns from multiple graph streams in real-time. The methods perform different amounts and types of individual-stream pre-processing in order to effectively reduce the size and arrival-rate of the data. These methods are: (1) sampling the data streams, (2) compressing the data streams based on known patterns, (3) mining individual streams first and then utilizing the mined patterns for performing multiple stream fusion. The methods will be evaluated using both artificial and real-world multi-stream graph data, and results will be disseminated via software releases and publications. This research will advance our knowledge and understanding of how to efficiently process multiple data streams represented as graphs in order to learn structural patterns in real time. The methods developed under this project represent a new level of scalability that is necessary to address today's big data challenges, as well as users' needs to quickly discover actionable intelligence.