GPU-Accelerated 𝜂-threshold Decomposition for Uncertain Graphs

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, codesigned 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 supernodeinduced 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.