用预测模型加速求解密集子图问题，线性时间逼近最优解。
Fast and Simple Densest Subgraph with Predictions
- 引入节点归属预测器，指导算法快速定位候选子图。
- 在真实图数据上实现近似比1-ε，且运行时间线性增长。
- 适合需要快速响应的图分析场景，如社交网络检测。
我们从学习增强算法的角度研究稠密子图问题及其NP难的至多k个顶点稠密子图变体。给定一个合理准确的预测器（例如机器学习分类器），可估计节点是否属于解集，我们设计了简单的线性时间算法，实现(1-ε)近似。最后，我们在真实图数据上展示了所提方法在至多k个顶点稠密子图问题上的有效性。
原文摘要 · Abstract (English)
We study the densest subgraph problem and its NP-hard densest at-most-$k$ subgraph variant through the lens of learning-augmented algorithms. We show that, given a reasonably accurate predictor that estimates whether a node belongs to the solution (e.g., a machine learning classifier), one can design simple linear-time algorithms that achieve a $(1-ε)$approximation. Finally, we present experimental results demonstrating the effectiveness of our methods for the densest at-most-$k$ subgraph problem on real-world graphs.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。