Close

Presentation

GraphSet: High Performance Graph Mining through Equivalent Set Transformations
DescriptionGraph 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.
Event Type
Paper
TimeTuesday, 14 November 20234pm - 4:30pm MST
Location405-406-407
Tags
Accelerators
Applications
Graph Algorithms and Frameworks
Performance Measurement, Modeling, and Tools
Programming Frameworks and System Software
Registration Categories
TP
Reproducibility Badges