International Team Developing New Algorithms for Streaming Graph Data

Four professors across the globe are collaborating to solve real-world problems in cybersecurity, health, and various areas of social science through a project called Streaming Graph Algorithms under the new Institute for Future Technologies, a partnership between New Jersey Institute of Technology (NJIT) and Ben-Gurion of the Negev University (BGU).

David Bader, distinguished professor and director of the Institute for Data Science at NJIT, and Michael Elkin,  professor in the department of computer science at BGU, are the project leads along with Ioannis Koutis, NJIT associate professor of computer science, and Ofer Neiman, BGU associate professor of computer science.

Many real-world data sets can be abstracted as a graph with vertices representing objects and edges between vertices representing the connections between them. When the data sets are small, analyzing the associated graph is usually straightforward.  However, as the data sets grow in size, new algorithmic techniques are needed to manipulate the resulting huge graphs in order to analyze and extract valuable information from them. For example, a graph may represent a transportation network where vertices are intersections and each edge is a road.  Quickly answering queries about routing in the network requires new algorithms for sparsifying the graph such that the reduced graph preserves many of the features of the original one, such as distances between vertices.

In other graph problems, such as analyzing network data in cybersecurity applications, the graph changes dynamically as new network traffic data arrives, making for an even more challenging problem of keeping track of the graph structure as the data “streams” in. Given this, rather than performing forensic analysis of security logs after a cybersecurity breach, the new streaming graph methods provide predictive analytics that prevent an attack before an intrusion occurs.

Together, the researchers are exploring how to address the sparsity and lack of locality in data, the need for scalable algorithms, the treatment of dynamically streamed data sets, and the development of frameworks for solving such problems on high-performance computers.

The researchers behind the Streaming Graph Algorithms project will take advantage of their initial results to seek additional funding from the National Science Foundation (NSF) in the U.S. and the U.S.–Israel Binational Science Foundation (BSF).