研究排序算法在恶意干扰下的稳定性，提出加权修正方法提升精度。
Entrywise Error Bounds for Spectral Ranking with Semi-Random Adversaries
- 针对半随机对抗者干扰的边采样，改进谱方法权重分配
- 加权后算法误差逼近均匀采样情形，理论性能恢复
- 适用于需要高鲁棒性的排名系统，如推荐与评估
Bradley-Terry-Luce（BTL）模型估计是基于成对比较数据对项目进行排序的成熟方法。尽管谱估计和最大似然估计在均匀采样图的场景下理论性能已充分研究，但将其推广到更广泛的随机图类别仍具挑战性。本文研究了谱算法在半随机对抗者干扰下的逐项误差，该对抗者可任意提升某些边的采样概率。结果表明，未加权谱方法的性能严重依赖于生成图的谱特性。进一步证明，通过适当重加权观测边以抵消对抗影响并恢复谱间隙，可实现逼近均匀采样图的渐近性能。最后，数值模拟验证了理论结论。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。