EAGER: Facilitating Graph Computation by Graph Sparsification

Florida State University, Tallahassee FL

Investigators

Abstract

Modern science and technology have witnessed in the past decade an explosive growth of networked systems giving rise to a vast ocean of data with completely transformed scale, structure, and complexity, which are often modeled and interpreted as graphs. However, real-world graph-structured data are voluminous and exhibit unprecedented complexity and unique challenges that render them extremely hard to manage, costly to ingest, and complicated to analyze. In this project, the PI will systematically investigate the principles, methodologies, and algorithms of graph sparsification, the objective of which is to simplify large-scale graphs into structure-enriched, quality-preserving graph summaries toward facilitating and optimizing a wide range of graph-based computations in real-world, large-scale graphs. This project will open a new research frontier for managing and understanding big graphs, facilitate the widespread availability of networked systems, and result in efficient, cost-effective, and scalable graph management, access, and summarization solutions for the whole modern, networked society. The PI plans to develop new foundations, principles, and algorithms for sparsifying big graph data, and systematically address a series of central challenges for graph sparsification: 1. What crucial structures or key properties of big graphs should be encoded in sparsified graph summaries. 2 How to sparsify big graphs efficiently, cost-effectively, and scalably. 3. How to employ sparsified graph summaries in support of graph-based computation and analytics, including, but not limited to, graph clustering, classification, query processing, and link prediction. The PI will build on his extensive background in graph data management to develop new graph sparsification methods, and integrate them toward facilitating large-scale graph computation in real-world graph databases and big graphs. In particular, the PI will apply and validate the proposed graph sparsification techniques in a series of protein-protein interaction networks, social networks, RNA molecule graph databases, and in-situ oceanographic graph databases. The project plays an integral part in educating next-generation professional workers and scholars especially from underrepresented groups, and contributing to K-12 outreach activities through the Florida State University Young Scholars program. Finally, data, system artifacts, and publications from the project will be disseminated broadly in the research community and to the public to enhance the infrastructure for research and education.