PhD Candidate: Yihua Wei
Abstract: Subgraph matching algorithms--such as graph pattern matching, motif counting, temporal subgraph matching, and continuous subgraph matching—are essential to many applications in bioinformatics, social network analysis, and cybersecurity. Despite extensive prior research on subgraph matching, the NP-hard time complexity of these algorithms makes them performance bottlenecks, especially on large-scale graphs. Therefore, there is growing interest in leveraging the massive parallelism of GPUs to accelerate these computations.
This dissertation presents four contributions that address key performance and programming challenges in accelerating various subgraph matching algorithms. These contributions fall into three technical directions:
Parallelization: We make two contributions in this direction, STMatch and DCSM. For graph pattern matching, STMatch introduces a stack-based recursion simulator to eliminate recursion overhead, a depth-first extension strategy with work stealing to mitigate load imbalance, and a loop-unrolling strategy to improve warp-level thread utilization. DCSM proposes a multi-version graph data structure for continuous subgraph matching to address data race issues when processing different requests concurrently.
Memory access efficiency: In this direction, we propose GCSM, which improves memory access efficiency for continuous subgraph matching by exploiting the highly skewed access frequency across graph regions. GCSM adopts a profiling-execution model that identifies frequently accessed data and places them in high-bandwidth or on-chip memory, significantly improving data locality.
Programming model: We propose Matcha, a domain-specific language for backtracking-based subgraph matching algorithms. Matcha leverages functional higher-order operators and a multi-level intermediate representation (IR) design to express a variety of algorithms while allowing the compiler to automatically perform domain-specific parallelization and memory optimizations.
These contributions provide a cohesive and extensible foundation for accelerating a broad class of subgraph matching algorithms. Beyond subgraph matching, the core ideas we propose can also be extended to a range of other irregular applications, such as backtracking algorithms, relational joins, and applications with irregular nested-loop structures.
Advisor: Peng Jiang
Location: MLH B-11 (Please contact Yihua Wei if you plan to attend: yihua-wei@uiowa.edu)