Incremental Strongly Connected Components with Predictions
For practitioners maintaining dynamic graphs, this work provides a way to leverage predictions to accelerate SCC maintenance, though the improvement is incremental over existing methods.
The paper introduces a learned data structure for incremental strongly connected components that uses predictions of edge arrival order to achieve nearly optimal runtime, with performance degrading gracefully as prediction error increases. Experiments on real datasets confirm practical speedups.
Algorithms with predictions is a growing area that aims to leverage machine-learned predictions to design faster beyond-worst-case algorithms. In this paper, we use this framework to design a learned data structure for the incremental strongly connected components (SCC) problem. In this problem, the $n$ vertices of a graph are known a priori and the $m$ directed edges arrive over time. The goal is to efficiently maintain the strongly connected components of the graph after each insert. Our algorithm receives a possibly erroneous prediction of the edge sequence and uses it to precompute partial solutions to support fast inserts. We show that our algorithm achieves nearly optimal bounds with good predictions and its performance smoothly degrades with the prediction error. We also implement our data structure and perform experiments on real datasets. Our empirical results show that the theory is predictive of practical runtime improvements.