用机器学习预测边的顺序，加速动态图强连通分量维护。
Incremental Strongly Connected Components with Predictions
- 基于预测的边序预计算部分解，提升插入效率。
- 预测准确时接近理论最优，误差增大时性能渐退。
- 实测验证理论效果，适合动态图场景应用。
预测算法是新兴领域，旨在利用机器学习预测来设计优于最坏情况的算法。本文将该框架应用于增量强连通分量（SCC）问题：图中n个顶点已知，m条有向边按时间顺序逐个到达，目标是每次插入后高效维护强连通分量。算法接收一个可能错误的边序列预测，并据此预计算部分解以支持快速插入。我们证明，当预测准确时，算法达到近乎最优复杂度；预测误差增大时，性能平滑下降。我们实现了该数据结构并在真实数据集上测试，实验表明理论预测与实际运行时间改善高度一致。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。