Efficient GPU-Accelerated Adaptive Minimum Cost Seed Selection

Abstract

Efficient influence estimation and seed selection are crucial to social network advertising and are widely studied in data management. We focus on adaptive minimum cost seed selection (AMCSS), which selects seed nodes adaptively over multiple rounds, to reach a target number η of influenced users while minimizing total seed cost. Prior work, notably ASTI with multi-root reverse reachable sets (mRR-sets), remains computationally expensive on large graphs, often taking hours to days even with CPU parallelism. We present GAAS, a GPU-accelerated method that integrates novel algorithmic and GPU-aware system designs to solve AMCSS in minutes. Processing mRR-sets involves irregular access patterns and variable-size samples, mismatching the GPU parallel architecture. Hence, we first develop a GPU-tailored mRR-set structure , GmRR, that assigns each thread block exclusive ownership of an equal-size segment with a circular layout, enabling efficient parallel mRR-set management while minimizing write contention. With GmRR, we design a GPU kernel ParallelGen to generate mRR-sets. Unlike prior work that regenerates mRR-sets from scratch in each round, we propose to update and reuse those from previous round, improving efficiency while requiring GPU-aware designs and rigorous theoretical analysis. Specifically, we design a ParallelUpdate kernel with theoretically grounded update rules that uses circular segment updates on GmRR for efficient mRR-set updates, together with a load-balancing scheme. We further devise a Select kernel for parallel seed selection. Integrating these together, GAAS efficiently solves AMCSS on GPUs with guarantees. Extensive experiments on large real-world graphs under different diffusion models show that GAAS is over an order of magnitude faster (up to 68.9×) than parallel CPU and GPU baselines, while the seed cost is among the lowest.