Uncertain (or Probabilistic) graphs have been ubiquitously used to represent noisy, incomplete, and inaccurate linked data in many emerging applications. Existing solutions are heavily time-consumed on even a simple node-to-node reliability query over uncertain graphs, which is a #P-hard problem, as they need to evaluate an exponential number of certain instances (``possible worlds") generated from the uncertain graph. Modern GPUs provide the massive amount of parallelism to efficiently process large-scale certain graph computation, but the challenges still exist due to their lack of the support for complex probabilistic nature of uncertain graphs. Specifically, the storage representation of an uncertain graph would be exponential on samples for reasonable accuracy. Traditional processing methods by storing each instance and then running certain graph analytic are deemed undesirable on GPU. Meanwhile, compared to conventional certain graph analytics, the probabilistic processing along each node-to-node path over an uncertain graph is much more computation-insensitive than memory-insensitive traversal.

To address these challenges, we adopt a unified indexing bit-aware path structure (BitPath) by pre-sampling ``possible world", which largely reduces the redundant irregular traversing and computation overhead, and propose to share and prune these pre-indexed BitPaths on parallel configurations. By taking advantage of GPUs, We present BPGraph, an efficient and scalable GPU-accelerated analytic framework that processes uncertain graphs using optimized fine-grained hybrid execution and GPU-friendly data formation after decomposing graph into more regular linked pieces. BPGraph proposes constructs for the uncertain graph applications on multi-accelerator programming. Meanwhile, several modern GPU-based features are exploited to accelerate the parallel execution, including cooperative groups and a finer-grained intra-GPU synchronization between parallel threads. Extensive experimental evaluations on widely real-world graphs and algorithms demonstrate that BPGraph significantly achieves significant speedup compared to CPU-based approaches.