Grace: Alleviating Reconstruction Cost in Dynamic Graph Processing Systems

Efficient dynamic graph processing is critical for real-time applications. Recent systems utilize hybrid layouts combining Packed Memory Array (PMA) and Compressed Sparse Row (CSR) structures to balance updating and computing efficiency. However, these systems face key challenges, including costly global copying and traversal during reconstruction, which in turn induce excessive costly rebalancing processes during graph updating, limiting performance under intensive updates. To mitigate these, existing solutions either compromise cache efficiency by relaxing memory contiguity or apply OS-level techniques without exploiting graph structural properties, leaving large optimization space unexplored. In this paper, we propose GRACE, a lightweight extension for PMA-based CSR systems that leverages graph structural properties to improve reconstruction and support efficient updates without sacrificing layout contiguity. Specifically, GRACE incorporates 1) a propertyguided reservation strategy that partitions the PMA into regions and applies tailored methods, minimizing copying and traversal during reconstruction while providing optimized layout for rebalancing, and 2) a cousin-aware rebalancing strategy that assesses the impact of the vertices and confines rebalancing to smaller ranges by exploiting cousin segments of PMA tree, reducing redundant relocation during insertion. We implement GRACE as a modular plugin atop representative dynamic graph processing systems, including PPCSR, Terrace, and VCSR. Experimental results show that GRACE effectively accelerates their reconstruction and achieves substantial improvements in graph updating efficiency while maintaining comparable computing performance.