PhD Dissertation Defense by YE Chang | Memory-Efficient Graph Processing on GPUs: Reducing Intermediate Data Structure Overhead

Memory-Efficient Graph Processing on GPUs: Reducing Intermediate Data Structure Overhead

ABOUT THE TALK

The increasing scale of real-world graphs in domains such as fraud detection, community detection, and biological analysis demands high-throughput, memory-efficient graph processing solutions. This dissertation addresses the challenge of reducing intermediate memory overhead in GPU-based graph processing through sketching, compression, and sampling techniques. These techniques are well-suited to a wide range of algorithms. In this dissertation, we select two representative examples, label propagation and subgraph counting, to demonstrate our contributions. 

Our first contribution is GLP, a GPU-accelerated label propagation framework that targets the problem of frequent label tracking under tight memory constraints. GLP incorporates Count-Min Sketch and compact GPU hash tables to track most frequent labels, significantly reducing the required memory.  Building upon this foundation, the second one introduces CGLP+, a memory-optimized framework for label propagation over compressed graphs. Traditional GPU frameworks assume full decompression of graph data prior to computation, which is often infeasible for large graphs.  CGLP+ addresses this by enabling partial decompression and in-place computation on compressed adjacency lists, thereby eliminating the need to load the entire graph into memory.

The final contribution is gSWORD, a GPU-based subgraph counting framework. While GLP and CGLP leverage sketching and compression techniques to reduce memory consumption for label propagation tasks, where the intermediate results are frequency counts, gSWORD targets the subgraph counting task, where the intermediate results consist of partial instances rather than numeric values. This framework leverages the massive parallelism of GPUs to accelerate iterative sampling algorithms for subgraph counting. Despite the embarrassingly parallel nature of the samples, there are unique challenges in accelerating subgraph counting due to its irregular computation logic. To address these challenges, we propose two GPU-centric optimizations for efficiency. 

Together, these contributions advance memory-efficient graph processing on GPUs, enabling more scalable, real-time processing with strong performance in both memory use and speed across diverse datasets.

SPEAKER BIOGRAPHY

Chang YE is a Ph.D. candidate at the School of Computing and Information Systems, Singapore Management University (SMU) under the guidance of Prof Yuchen LI. Before joining SMU, Chang received his BSc and MSc degrees in the area of Electronic Engineering from the Xidian University, in 2014 and 2018, respectively. His research interests are graph analytics and heterogeneous computing.