GPU-Accelerated ๐œ‚-threshold Decomposition for Uncertain Graphs

vldb26-2942 ยท Regular Research ยท Yu Chen, Chong Liu, Qing Liu, Zhonggen Li, Yifan Zhu, Yunjun Gao
Abstract

The ๐œ‚-threshold decomposition in uncertain graphs, which calculates the ๐œ‚-thresholds for each vertex, is a fundamental problem in graph analysis. However, the current CPU-based peeling algorithm suffers from prohibitive computational costs, making it infeasible for time-sensitive applications such as fraud detection and dynamic public opinion monitoring. To address this, we introduce Gatd, the first GPU-accelerated framework for ๐œ‚-threshold decomposition, co-designed with GPU architecture to enable efficient parallelization. Given that the problem is a computationally intensive per-vertex task dominated by probability computation, thereby constraining efficiency, Gatd incorporates three enhancement modules: (i) Redundancy reduction through lower-bound pruning, leveraging safety thresholds from prior iterations, and batch updating of vertices sharing the same ๐œ‚-threshold; (ii) Adaptive parallelization utilizing dynamically sized thread collaboration groups and hybrid scheduling to match computational resources with dynamic workloads; and (iii) Three-stage load balancing based on neighbor grouping, work stealing, and hierarchical merging to mitigate supernode-induced imbalance. Extensive experiments on diverse uncertain graphs demonstrate that the optimized Gatd achieves speedups of up to four orders of magnitude over state-of-the-art CPU-based methods and existing GPU-based graph processing frameworks, facilitating efficient decomposition even for large-scale networks.

Assigned reviewers

No reviewers assigned yet.

Candidates from the panel ranked by taxonomy affinity

#ReviewerMatchLoadWhy