SHF: Small: Scalable and Versatile Evolving Graph Analytics

About This Grant

Since graphs can readily represent entities and relationships among them, they are widely used to represent large volumes of data from domains ranging from transportation networks to biological networks. When the data has an associated temporal dimension, it is represented as an evolving graph that consists of a sequence of snapshots of the graph at different points in time. Mining of large evolving graphs involves understanding trends in changes to relevant graph properties over a chosen time window. Since evolving graphs are extremely large, evaluating queries over a sequence of snapshots is both compute- and data-intensive. The irregular structure of real-world graphs and the iterative nature of graph queries that require multiple passes over graph data impose further challenges to optimizing the evaluation of temporal queries. This project aims to dramatically improve parallel evaluation times and memory requirements of evaluating temporal queries on evolving graphs. Building a powerful system will accelerate discoveries in fields that employ evolving graph analytics. In addition, it will result in training graduate students in high-performance computing, an area of national need. The software and graph data developed during this project will be available to other researchers. The technical aims of this project are to substantially advance the state of the art of evolving graph analytics by developing highly scalable systems and to expand the scope of supported analytics queries greatly. For graphs that have been evolving over a long period of time, two classes of challenges are addressed. The first class requires substantially improving the efficiency of evolving graph processing. The large sizes of graphs and a large number of snapshots lead to high query evaluation costs. Novel approaches that exploit the slowly changing nature of an evolving graph are needed to address these challenges. The second class aims to carry out relevant snapshot identification and planning problems. Relevant snapshots identification omits snapshots that do not contribute to property change, while planning considers goal-oriented evolution of the graph to meet future needs. 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.