Mind the Gap: The Disconnect Between Synthetic and Natural Edge Weights in Parallel Single-Source Shortest Path
For researchers evaluating parallel SSSP algorithms, this work highlights a critical flaw in current benchmarking practices that can lead to misleading conclusions about algorithm performance.
The paper shows that using synthetic uniform edge weights in benchmarking parallel SSSP algorithms biases performance results, inverting the performance hierarchy compared to real-world heavy-tailed weight distributions. Evaluation of seven algorithms on 17 real-world graphs confirms severe sensitivity to weight distributions.
Scientific research works often evaluate Parallel Single-Source Shortest Path (SSSP) algorithms using synthetic, uniformly distributed edge weights. However, real-world graphs exhibit very different, often heavy-tailed, weight distributions. This creates a disconnect between how algorithms are evaluated and their real-world performance, since most SSSP implementations inherently rely on the weight distribution for parameter tuning and work efficiency. In this paper, we explore whether current benchmarking methods unintentionally bias the performance results of these algorithms. To this end, we statistically characterize the weight distributions of 17 real-world graphs from a variety of domains and contrast them with six synthetic distributions used in the literature. Through a comprehensive evaluation of seven state-of-the-art parallel SSSP algorithms, we demonstrate severe sensitivity to edge weights, and show that evaluating with synthetic uniform weights alters optimal parameter configurations and can invert the performance hierarchy. These findings challenge existing benchmarking standards and offer practical insights for rigorous SSSP algorithm design.