준무작위 적대적 공격 환경에서의 스펙트럼 순위 결정(Spectral Ranking)에 대한 원소별 오차 범위

Bradley-Terry-Luce (BTL) 모델 추정은 쌍체 비교 (pairwise comparisons) 데이터셋이 주어졌을 때 아이템 집합의 순위를 매기는 잘 확립된 전략입니다. 스펙트럼 (spectral) 및 최대 가능도 추정 (maximum likelihood estimation)과 같은 BTL 추정 방법의 이론적 성능은 균일하게 샘플링된 그래프 (uniformly sampled graphs) 영역에서는 잘 연구되어 왔으나, 이러한 결과를 더 넓은 범위의 무작위 그래프 (random graphs) 클래스로 일반화하는 것은 어려운 과제로 증명되었습니다. 본 연구에서는 특정 에지 (edges)의 샘플링 확률을 임의로 높일 수 있는 준무작위 적대자 (semi-random adversary)에 맞서 스펙트럼 알고리즘 (spectral algorithms)의 원소별 오차 (entry-wise error)를 조사합니다. 우리는 가중치가 없는 스펙트럼 방법 (unweighted spectral method)의 성능이 생성된 그래프의 스펙트럼 특성 (spectral properties)에 크게 의존한다는 것을 발견했습니다. 나아가, 적대자의 공격에 대응하고 스펙트럼 간극 (spectral gap)을 회복하기 위해 관측된 에지에 적절히 가중치를 다시 부여함으로써, 균일하게 샘플링된 그래프의 성능에 근접하는 점근적 성능 (asymptotic performance)을 회복할 수 있음을 보여줍니다. 마지막으로, 우리의 이론적 발견을 뒷받침하는 수치 시뮬레이션 (numerical simulations)을 제공합니다.