Collaborative Research: SHF: Small: Scalable Algorithmic and Software Foundations for Subgraph Counting and Enumeration

NSF Award Search · 01002526DB NSF RESEARCH & RELATED ACTIVIT · $270,000 · view on nsf.gov ↗

Abstract

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‑

Key facts

NSF award ID
2453323
Awardee
Yale University (CT)
SAM.gov UEI
FL6GV84CKN57
PI
Quanquan C Liu
Primary program
01002526DB NSF RESEARCH & RELATED ACTIVIT
All programs
SMALL PROJECT, HIGH-PERFORMANCE COMPUTING
Estimated total
$270,000
Funds obligated
$270,000
Transaction type
Standard Grant
Period
07/01/2025 → 06/30/2028