做排序算法或对抗鲁棒性研究的团队，这篇论文给出了半随机对抗下谱方法的理论误差界，并提出了有效的重加权策略，值得关注。
本文研究了在Bradley-Terry-Luce (BTL)模型下，当数据受到半随机对抗攻击（即某些边的采样概率被人为提升）时，谱排序算法的逐项误差表现。研究发现，未加权的谱方法性能高度依赖于生成图的谱性质，而通过对观测边进行适当重加权以恢复谱间隙，可以接近均匀采样图下的渐近性能。理论结果通过数值模拟得到了验证。这项工作为对抗环境下的排序算法提供了理论保证。
Entrywise Error Bounds for Spectral Ranking with Semi-Random Adversaries
Bradley-Terry-Luce (BTL) model estimation is a well-established strategy to rank a collection of items given a dataset of pairwise comparisons. Although the theoretical performance of BTL estimation methods, such as spectral and maximum likelihood estimation, is well studied in the regime of uniformly sampled graphs, generalizing such results to a wider class of random graphs has proved challenging. In this work, we investigate the entry-wise error of spectral algorithms against a semi-random adversary that can arbitrarily boost the sampling probabilities of certain edges. We find that the performance of the unweighted spectral method is heavily dependent on the spectral properties of the generated graph. Furthermore, we show that asymptotic performance approaching that of uniformly sampled graphs can be recovered by appropriately reweighting the observed edges to counteract the adversary and restore the spectral gap. Finally, we provide numerical simulations that support our theoretical findings.