CRII: III: Structure-aware Graph Compressing: From Algorithms to Applications

Graph mining is an emerging field with a wide spectrum of applications across many disciplines, such as social media and healthcare. Examples of applications include finding groups of users in social networks (e.g., Facebook), which is useful for a personalized recommendation, and detecting drug-drug interactions, which may cause dangerous side effects on health.

In graph mining, many useful methods can be applied to small graphs effectively. However, the ever-increasing size of real-world networks is a major challenge for these methods due to their high computational and space costs. This project aims at developing novel graph compression (summarization) methodologies that facilitate efficient analysis of large graphs and advancing a wide spectrum of graph-related applications.

Graph compression aims to create a smaller graph from a massive graph. Compressing graphs achieves several benefits, including but not limited to 1) significant speed-up for current graph mining algorithms, 2) memory space and communication cost reduction, 3) improved data privacy, 4) more effective graph visualization. This project will provide research opportunities to graduate students, especially female and underrepresented students, in graph mining and its real-life applications.

The PI will also incorporate the results of the research in undergraduate and graduate-level courses.

Graph compression algorithms reduce the complexity and size of large graphs while maintaining the crucial information of the original graph in the smaller graph. Such reductions are essential to scale up or scale out existing algorithms to better manage, query, store, and display them. The investigator will design graph compression methods that preserve the desired structural information of graphs, including similarity and cohesiveness, specific to the selected graph mining problems.

This project will: 1) explore the spatial locality property of graphs by taking the structural information from different aspects, including similarity of nodes and cohesiveness of subgraphs; 2) develop the corresponding novel structure-aware compression methods to tackle the challenges brought by large real-world networks; and 3) build more tailored architectures with proposed compression methods for various problems, including network embedding and community search and evaluate them on real-world applications such as link prediction, node classification, anomaly detection, and community detection. Its outcomes will be disseminated through publications, tutorials, workshops, as well as open-source tools, code, and datasets.

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.