在 Erdős-Rényi 随机图中，植入子图的检测问题经过广泛研究，形成了丰富的统计与计算阈值特征。然而，大多数研究假设了纯随机的生成模型，这使得算法在面对真实世界的扰动时可能显得脆弱。本研究首次探讨了半随机模型下的植入子图检测问题，其中敌手可以在图被揭示给统计学家之前，删除植入子图以外的边。这一过程使得统计学家无法得知哪些边被删除，给推断任务带来了根本挑战。
我们确立了在这一半随机模型下的基本统计限制，揭示出明显的二分法。具体而言，针对最大密度远小于对数级的植入子图，检测在敌手存在的情况下信息论上变得不可能，而在经典随机模型中对于某些植入子图则是可行的。相对而言，对于远大于对数密度的子图，统计限制基本保持不变；我们证明了最优的（尽管计算上不可行的）似然比检验依然是鲁棒的。
在这些统计边界之外，我们设计了一种新的计算高效且鲁棒的检测算法，并为其性能提供了严格的统计保证。我们的研究建立了首个植入子图检测的鲁棒框架，并为半随机模型的研究、计算与统计的权衡及图推断问题中的鲁棒性开辟了新的方向。
博主点评： 本文为植入子图检测提供了创新的半随机模型视角，解决了传统随机模型下的脆弱性问题，展示了在敌手干扰下的统计极限与算法鲁棒性，为未来研究指明了方向。其提出的算法与理论结果将对图论研究领域产生深远影响。