Scalable Algorithmic and Software Foundations for Subgraph Counting and Enumeration

This award supports the development of advanced computational methods for tracking and analyzing evolving patterns in large-scale networks. Patterns of connections among entities, known as subgraphs, underpin insights in domains such as social interactions, biological processes, financial transactions, and communication systems. Real-time analysis of how these patterns form and dissolve can enable early detection of disease outbreaks, improved understanding of social dynamics, and enhanced network security. By creating scalable and accessible tools for dynamic network analysis, this project will advance the national interest in data-driven discovery across science, technology, and public welfare.

The project will pursue three integrated research thrusts. First, it will develop novel algorithms with provable efficiency guarantees for counting and enumerating subgraphs in the batch-dynamic model on parallel and distributed systems. Second, it will design and implement high-level programming frameworks and data structures tailored to dynamic graph workloads, including graphics processing unit (GPU) and distributed implementations, to facilitate practical adoption. Third, it will integrate the new algorithms and frameworks into an open-source analysis platform and conduct comprehensive evaluations on high-performance computing clusters and cloud resources. These efforts will yield the first provably-optimal dynamic subgraph counting algorithms for higher-order patterns, query-based enumeration techniques, and user-friendly software enabling researchers to perform real-time analysis on evolving networks.

Investigators:

• David Bader, New Jersey Institute of Technology (Principal Investigator: CCF-2453324)
• Quanquan Liu, Yale University (Principal Investigator CCF-2453323)

Links

• NSF OAC-2453324