Technical Papers Archive

GraphSet: High Performance Graph Mining through Equivalent Set Transformations

Authors: Tianhui Shi, Jidong Zhai, Haojie Wang, Qiqian Chen, Mingshu Zhai, Zixu Hao, Haoyu Yang, and Wenguang Chen (Tsinghua University, China)

Abstract: Graph mining is of critical use in a number of fields such as social networks, knowledge graphs, and fraud detection. As an NP-complete problem, improving computation performance is the main target for current optimizations. Due to excellent performance, state-of-the-art graph mining systems mainly rely on pattern-aware algorithms. Despite previous efforts, complex control flows introduced by pattern-aware algorithms bring large overhead and also impede further acceleration on heterogeneous hardware.

To address these challenges, we propose a set-based equivalent transformation approach for the optimization of pattern-aware graph mining applications, which can leverage set properties to eliminate most control flows and reduce computation overhead exponentially. We implement a high-performance pattern-aware graph mining system supporting both CPU and GPU, namely GraphSet, to automatically apply these transformations. Evaluation results show that GraphSet outperforms state-of-the-art cross-platform and hardware-specific graph mining frameworks by up to 3384.1x and 243.2x (18.0x and 10.2x on average), respectively.




Back to Technical Papers Archive Listing