arXiv CSopen access

Entrywise Error Bounds for Spectral Ranking with Semi-Random Adversaries

arXiv:2605.23854v1 [cs.LG] 22 May 2026

Entrywise Error Bounds for Spectral Ranking with Semi-Random Adversaries Dongmin Lee∗

Anuran Makur

Japneet Singh

[email protected] Department of Computer Science Purdue University West Lafayette, IN, USA

[email protected] Department of Computer Science Elmore Family School of Electrical and Computer Engineering Purdue University West Lafayette, IN, USA

[email protected] Elmore Family School of Electrical and Computer Engineering Purdue University West Lafayette, IN, USA

Abstract

is often clustered and non-uniform. For example, when ranking chess players, there might be more matches observed between players who live in the same country. Unfortunately, the best known analyses of BTL estimation on Erdős-Rényi graphs do not easily generalize to other graph models (see, e.g., [51] which studies deterministic graphs), because they critically rely on the superior uniformity of such random graphs, such as the concentration of node degrees, in order to derive the tightest bound possible. In the regime of general deterministic graphs where such properties cannot be guaranteed, obtaining a tight bound that holds for all graphs is difficult. Indeed, known results in the general setting such as [13, 38] fail to bound the ℓ ∞ error as tightly as possible for uniformly sampled graphs. Thus, it is natural to seek a middle ground between the restrictiveness of uniformly sampled graphs and the intractability of arbitrary deterministic graphs. To this end, we consider the semi-random adversary model, where an adversary can (with some restrictions) perturb an initially uniform sample. The semi-random adversary model has found widespread acceptance in many different areas such as graph theory (especially graph coloring and partitioning) [2, 5, 23, 42], matrix completion [16, 27, 36], and preconditioning [34]. Recently, [55] investigated the effectiveness of the MLE method for BTL estimation on semi-random graphs. However, to the best of our knowledge, such an analysis has not been established for the second major paradigm of BTL estimation—the spectral method. In this work, we address this direction by analyzing the theoretical performance of the spectral method against a semi-random adversary. In our semi-random adversary model, the adversary is allowed to choose a different sampling probability for each possible edge of the graph, as long as it is not smaller than some base probability 𝑝. This model encompasses important random graph models such as the stochastic block model (SBM) [30] that better represent real-world data than standard Erdős-Rényi models. Since a graph generated by such an adversary appears to contain no less information than an equivalent Erdős-Rényi graph with the same 𝑝, it may seem that the adversary’s actions can only benefit us. However, this is not true; it is a well-known phenomenon that adding edges to a graph can paradoxically hurt the spectral properties that spectral methods rely on. For example, as Figure 1 illustrates, adding an edge to a graph can, counter-intuitively, reduce the second smallest eigenvalue of its normalized Laplacian (also called the spectral gap) [24]. Indeed, [19] demonstrated that the addition of a random edge to an Erdős-Rényi graph decreases the spectral gap with positive probability.

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.

Keywords Preference learning, Bradley-Terry-Luce model estimation, Semirandom adversary

1

Introduction

Pairwise preference learning is the classic problem of estimating preferences for a collection of 𝑛 items given a set of pairwise comparisons. The problem has many applications including sports rankings [20], recommendation systems [3], and search engine algorithms [49]. Recently, the problem has also attracted significant attention in the machine learning community as a practical approach to align large language model (LLM) outputs with human feedback (see, e.g., [18, 48]). A popular model for this problem is the Bradley-TerryLuce (BTL) model [8, 41, 50, 56], which assumes that each item 𝑖 is associated with a latent score 𝛼𝑖 > 0 such that the probability of item 𝑖 being preferred over item 𝑗 is 𝛼𝑖 /(𝛼𝑖 + 𝛼 𝑗 ). There are two broad paradigms to estimate the score vector 𝜶 = (𝛼 1, . . . , 𝛼𝑛 ) from partially observed pairwise comparison graphs: maximum likelihood estimation (MLE) [25, 31, 51] and spectral algorithms [22, 32, 33, 47]. Under well-behaved settings, such as Erdős-Rényi comparison graphs, it is known that both methods are optimal in terms of sample complexity [14]. However, assuming each edge to be independent and identically distributed might not be a realistic assumption, as real-life data ∗ The author ordering is alphabetical.

1

Lee, Makur, and Singh

– We first obtain error bounds for the generic case, where no assumptions are made about the graph or reweighting procedure (Theorem 4.1). – Next, we derive error bounds for semi-randomly generated graphs using a specific reweighting procedure (Theorem 4.2). • We present empirical results that demonstrate how our weighted spectral method can counteract the effect of a semi-random adversary that chooses edge weights to degrade the spectral gap (Section 6). However, we emphasize that our work is primarily theoretical in nature.

→

𝜆𝑛−1 (𝐿 sym ) ≈ 0.423

𝜆𝑛−1 (𝐿 sym ) ≈ 0.346

Figure 1: A visualization of how adding an edge to a graph can paradoxically reduce its spectral gap, 𝜆𝑛−1 (𝐿 sym ) (the second smallest eigenvalue of the normalized Laplacian).

1.2

Our theoretical analysis focuses on the entry-wise, or ℓ ∞ , loss, as it is the most relevant metric for many important applications, such as top-𝐾 ranking [14, 15, 55] and hypothesis testing [39, 43, 44]. We begin by studying the performance of the vanilla spectral method (rank centrality [47]) against a semi-random adversary and find that the same entry-wise error bounds as those of uniform edge sampling can be obtained, provided that the spectral gap of the semirandomly generated graph can be lower bounded by some constant with high probability. Furthermore, we highlight a certain class of stochastic block models (SBMs) as an example of a non-Erdős-Rényi random graph that satisfies the spectral gap condition. In addition, to overcome the spectral gap requirement, we take inspiration from [55] to introduce an edge-weighted variant of the spectral method. Intuitively, the purpose of the reweighting is to undo the adversary’s efforts to weaken the graph’s spectral gap. We argue that such a reweighting must be possible by invoking a monotone coupling argument, showing that there must exist a subgraph of a semi-randomly generated graph that recovers the spectral properties of an Erdős-Rényi graph, then noting that edge reweighting is the continuous relaxation of taking a subgraph. We first present a generic error bound of the weighted spectral method that holds for any weighting procedure. Next, under the reweighting scheme proposed in [55], we show that weighted spectral ranking of semi-random graphs can maintain error bounds consistent with Erdős-Rényi graphs when the graph is sufficiently dense. We conclude with numerical simulations to support our theoretical results.

1.1

Related Work

The BTL model [8, 41, 50, 56] is perhaps one of the most widely adopted framework to model outcomes of pairwise comparisons across a diverse range of domains, including sports [4, 10, 32, 45], psychology [46], animal behavior [1], and ranking scientific journals [53]. Recently, it has also found use in the machine learning community for tasks such as reinforcement learning from human feedback (RLHF) [18, 48] and ranking LLMs [17]. Often the objective is to estimate the parameters of the BTL model (in order to find a ranking or determine the top 𝑘 items), and many techniques have been developed to tackle this problem, most notably MLE methods [25, 31, 51, 52, 56] and spectral methods [22, 32, 47] (and hybrids of the two such as [15]), but also least-squares [29], non-parametric [6, 11], and Bayesian [1, 9, 28] approaches. There exists a large body of work that focuses on finding theoretical error bounds for these BTL estimation methods under certain graph configurations, such as round-robin tournaments (i.e., complete graphs) [52] and general fixed graphs [13, 22, 38, 47]. In particular, the Erdős-Rényi model has attracted significant attention thanks to its simplicity and favorable statistical properties. For example, [47] bounds the ℓ 2 error of the spectral method on Erdős-Rényi random graphs and general graphs, while [12, 14] refine the former’s results and also bound the ℓ ∞ errors of the spectral and MLE methods, finding both to be asymptotically optimal (though with differing leading constants). On the other hand, [26] finds non-asymptotic entry-wise error bounds for the spectral and MLE methods under the Erdős-Rényi model and also presents some results for heterogeneously sampled graphs (which bears some similarities to our semi-random model, but unlike our model, requires edge sampling probabilities to have bounded dynamic range). Meanwhile, works such as [21, 22, 35] analyze the error bounds of estimators for the Plackett-Luce (PL) model, which is a generalization of the BTL model for multi-way comparisons. [55] introduced the semi-random adversary model in the context of BTL estimation and demonstrated that a weighted MLE method can achieve similar estimation guarantees to those of uniform sampling against a semi-random adversary. We remark that the use of reweighting as a technique to counteract a semi-random adversary has been studied in other contexts as well, such as matrix completion [16] and linear regression [34].

Contributions

We summarize our contributions as follows. • We obtain entry-wise error bounds for BTL estimation with the unweighted spectral method on semi-randomly generated graphs (Theorem 3.1). – Notably, we recover bounds consistent with [14] when the spectral bound of the canonical Markov matrix is lower bounded by a nonzero constant with high probability, as is the case for Erdős-Rényi graphs (Corollary 3.2). – Furthermore, we generalize this result to stochastic block models, showing that certain classes of SBMs preserve the spectral gap and thus allow error bounds comparable to those of Erdős-Rényi graphs to be attained (Proposition 3.4). • We describe and analyze a variant of the spectral method that reweights edges to improve the spectral properties of the stochastic matrix in Section 4.1.

1.3

Notation

We use the following notational conventions throughout this work. We represent vectors with lowercase bold letters and matrices 2

Entrywise Error Bounds for Spectral Ranking with Semi-Random Adversaries

with uppercase letters. Let [𝑛] = {1, 2, . . . , 𝑛}. ∥ · ∥ 𝑝 represents the ℓ 𝑝 norm for vectors and the corresponding induced norm for matrices. Given a vector 𝝅, we define the vector norm ∥𝒙 ∥ 𝝅 ≜ Í ( 𝑛𝑖=1 𝜋𝑖 𝑥𝑖2 ) 1/2 and the corresponding left operator norm ∥𝐴∥ 𝝅 ≜ sup ∥𝒙 ∥ 𝝅 =1 ∥𝒙 T𝐴∥ 𝝅 . Given a matrix 𝐴, 𝜆𝑖 (𝐴) refers to the 𝑖th largest eigenvalue of 𝐴 in absolute value. We use standard BachmannLandau asymptotic notation, e.g., 𝑓 (𝑛) = 𝑂 (𝑔(𝑛)) if there exists some constant 𝑀 > 0 such that |𝑓 (𝑛)| ≤ 𝑀𝑔(𝑛) for all 𝑛 ≥ 1. We use the term “with high probability” to describe events that occur with probability at least 1 − 𝑂 (𝑛 −𝑡 ) for some 𝑡 ≥ 1.

adversary model. Suppose that one compiles a database of pairwise comparisons between uniformly sampled items in some set 𝐴. In the middle of the data collection process, the scope of the experiment is expanded, and the set of items is updated to some superset of the original set, 𝐴′ ⊃ 𝐴. As a result, every potential pair in {(𝑖, 𝑗) ∈ 𝐴′2 : 𝑖 < 𝑗 } has some base probability 𝑝 > 0 of being observed, but pairs in 𝐴2 will have a higher probability of being observed and thus will be overrepresented in the dataset. Therefore, this dataset follows the semi-random observation graph model. As this example demonstrates, the semi-random adversary in our model is not necessarily an “attacker” but a theoretical construct that is useful to characterize the worst-case behavior of a wider class of random graphs that simpler models like the Erdős-Rényi model cannot capture.

2 Problem Formulation 2.1 Bradley-Terry-Luce Model We consider a set of 𝑛 items, each labeled 𝑖 ∈ [𝑛]. Under the BTL model, we assume that each item 𝑖 is associated with an underlying score (or skill) parameter 𝛼𝑖 > 0 such that the probability of item 𝑗 being preferred over 𝑖, 𝑝𝑖 𝑗 , is given as 𝛼𝑗 ∀(𝑖, 𝑗) ∈ [𝑛] 2 such that 𝑖 ≠ 𝑗, 𝑝𝑖 𝑗 ≜ . 𝛼𝑖 + 𝛼 𝑗

2.3

Spectral BTL Estimation

The goal of BTL estimation algorithms is to estimate the underlying score vector 𝜶 given observed comparison outcomes. Since the score vector is scale-invariant (i.e., multiplying 𝜶 by any nonzero constant does not affect the induced probabilities 𝑝𝑖 𝑗 ), we normalize 𝜶 to obtain the canonical score vector to be estimated,   1 𝛼 1 · · · 𝛼𝑛 . 𝝅 = Í𝑛 (2) 𝛼 𝑖=1 𝑖

We assume that the dynamic range of the scores is upper bounded by a constant ℎ, i.e., max𝑖 ∈ [𝑛] 𝛼𝑖 ≤ ℎ. (1) min𝑖 ∈ [𝑛] 𝛼𝑖

Note that the dynamic range assumption in (1) implies that

Note that this implies ∀𝑖 ∈ [𝑛],

1 ℎ ∀(𝑖, 𝑗) ∈ [𝑛] such that 𝑖 ≠ 𝑗, ≤ 𝑝𝑖 𝑗 ≤ . 1+ℎ 1+ℎ 2

2.2

thus √ √ 1 𝑛 ℎ ∥𝝅 ∥ ∞ ≤ ∥𝝅 ∥ 2 ≤ 𝑛∥𝝅 ∥ ∞ ≤ √ , √ ≤ ℎ ℎ 𝑛 𝑛 √︂ √︂ 1 ℎ ∀𝒗 ∈ R𝑛 , ∥𝒗 ∥ 2 ≤ ∥𝒗 ∥ 𝝅 ≤ ∥𝒗 ∥ 2, 𝑛ℎ 𝑛 1 ∀𝐴 ∈ R𝑛×𝑛 , ∥𝐴∥ 2 ≤ ∥𝐴∥ 𝝅 ≤ ℎ∥𝐴∥ 2 . ℎ Although there are several methods to estimate 𝝅, the main focus of this work is the spectral method (also called rank centrality) [47]. Given G and the true probabilities 𝑝𝑖 𝑗 , we can define the canonical Markov matrix 𝑆 ∈ [0, 1] 𝑛×𝑛 as

Semi-Random Observation Graph Model

Let G = (V, E) be the (undirected) observation graph that encodes observed comparisons, i.e., (𝑖, 𝑗) ∈ E and ( 𝑗, 𝑖) ∈ E if and only if items 𝑖 and 𝑗 are compared together. Given a parameter 𝑝 ∈ [0, 1], a semi-random adversary generates the observation graph G by picking each edge (𝑖, 𝑗) with 𝑖 < 𝑗 independently with probability 𝑞𝑖 𝑗 ∈ [𝑝, 1]. Note that if 𝑝 satisfies 𝑛𝑝 ≥ 𝑐 0 log(𝑛) for some fixed 𝑐 0 > 1, G is connected with high probability. Let 𝑑 min and 𝑑 max be the minimum and maximum degree of the graph respectively. Let 𝑘 be the number of observed comparisons for each pair (𝑖, 𝑗) ∈ E with 𝑖 < 𝑗. For simplicity, we assume that the number of comparisons is identical for every pair; our analysis can be extended to the case where the number of comparisons varies across pairs. The observed outcomes can be modeled as a sequence of independent Bernoulli random variables

𝑝𝑖 𝑗   , if (𝑖, 𝑗) ∈ E,   𝑑  Í 𝑆𝑖 𝑗 ≜ 1 − 𝑑1 𝑙:(𝑖,𝑙 ) ∈ E 𝑝𝑖𝑙 , if 𝑖 = 𝑗, (3)    0, otherwise,  where 𝑑 = 𝑑 max . Under the assumption that G is connected, the Markov chain is aperiodic (since 𝑆𝑖𝑖 > 0 for all 𝑖 ∈ [𝑛]), thus 𝑆 has a unique stationary distribution that can be shown to equal 𝝅 [37]. Motivated by this property, we can similarly define the empirical Markov matrix 𝑆ˆ using the empirical probabilities 𝑝ˆ𝑖 𝑗 derived from the observations. ˆ   𝑝𝑑𝑖 𝑗 , if (𝑖, 𝑗) ∈ E,    Í 𝑆ˆ𝑖 𝑗 ≜ 1 − 𝑑1 𝑙:(𝑖,𝑙 ) ∈ E 𝑝ˆ𝑖𝑙 , if 𝑖 = 𝑗,    0, otherwise.  Since 𝑆ˆ will converge to 𝑆 as 𝑘 → ∞, the spectral method obtains an approximation of 𝝅 (the normalized score vector) computes the stationary distribution 𝝅ˆ of 𝑆ˆ (i.e., its principal eigenvector).

𝑍𝑖(𝑚) ∼ Bernoulli(𝑝𝑖 𝑗 ) 𝑗 for all 𝑚 ∈ [𝑘] and (𝑖, 𝑗) ∈ E (with 𝑖 < 𝑗), such that 𝑍𝑖(𝑚) = 1 if 𝑗 𝑗 beat 𝑖 in the 𝑚-th comparison and 𝑍𝑖(𝑚) = 0 otherwise. Let 𝑗 𝑍𝑖 𝑗 ≜

𝑘 ∑︁

ℎ 1 ≤ 𝜋𝑖 ≤ , 𝑛ℎ 𝑛

𝑍𝑖(𝑚) 𝑗

𝑚=1

denote the total number of times 𝑗 beats 𝑖. Then, 𝑍𝑖 𝑗 𝑝ˆ𝑖 𝑗 ≜ 𝑘 is the empirical probability of 𝑗 beating 𝑖. Next, to provide intuition, we provide a simple example of a situation where the observation graph will follow the semi-random 3

Lee, Makur, and Singh

3 Main Results on Spectral Method 3.1 Entry-Wise Error Bounds

quantity) of the graph (see, e.g., [13, 47, 51]). We emphasize, however, that the spectral gap is not the only piece in the puzzle; obtaining tight bounds as in Theorem 3.1 requires each term of the error to be carefully decomposed and controlled. The key takeaway from this result is that when the spectral gap is lower bounded by a constant with high probability, the resulting error bounds are consistent with those for uniform sampling as derived in [14]. Using the fact that Erdős-Rényi graphs preserve the spectral gap with high probability [47], we can recover the results of [14] under uniform sampling in the following corollary.

In this section, we establish entry-wise error bounds for the (unmodified) rank centrality algorithm when applied to an observation graph generated by a semi-random adversary. We show that the vanilla rank centrality algorithm (without modifications such as reweighting or trimming) maintains its entry-wise error bounds under a semi-random adversary as long as the spectral gap 1−𝜆2 (𝑆) of the canonical Markov matrix 𝑆 is sufficiently preserved, as the following theorem highlights.

Corollary 3.2 (Error Bound for Erdős-Rényi Graphs). Suppose the observation graph G follows an Erdős-Rényi model with edge sampling probability 𝑝. Then, there exist constants 𝑐 0 > 1, 𝑐 1 > 0 such that for 𝑛𝑝 ≥ 𝑐 0 log(𝑛), the approximate score vector 𝝅ˆ estimated by the spectral method satisfies √︄ log(𝑛) ∥ 𝝅ˆ − 𝝅 ∥ ∞ ≤ 𝑐1 ∥𝝅 ∥ ∞ 𝑛𝑝𝑘

Theorem 3.1 (Entry-Wise Error Bounds for Unweighted Spectral Method). Assume that the observation graph G is generated by a semi-random model with edge probabilities 𝑞𝑖 𝑗 ∈ [𝑝, 1] for some constant 𝑝 ∈ (0, 1]. Let 𝑆 be the canonical Markov matrix of G as defined in (3). Suppose that !2 ∑︁ ∑︁ ∀𝑖 ∈ [𝑛], 𝑛 𝑞𝑖2𝑗 ≤ 𝑠 𝑞𝑖 𝑗 (4) 𝑗:𝑗≠𝑖

𝑗:𝑗≠𝑖

with probability at least 1 − 𝑂 (𝑛 −5 ).

holds for some fixed constant 𝑠 > 1, and that the spectral gap condition 1 (5) 𝑛5 holds for some constant 0 < 𝛾 < 1. Then, there exist constants 𝑐 0 ≥ 10240ℎ 2 /𝛾 2 , 𝑐 1 > 0, and 𝑐 2 > 0 such that for all 𝑝, 𝑘 satisfying 𝑛𝑝 ≥ 𝑐 0 log(𝑛) and 𝑘 ≥ 5, the approximate score vector 𝝅ˆ estimated by the spectral method satisfies   √︄ log(𝑛) ∥ 𝝅ˆ − 𝝅 ∥ ∞ 𝑐1 + 𝑐2 ≤ ∥𝝅 ∥ ∞ 𝛾 𝑛𝑝𝑘

3.2

P(1 − |𝜆2 (𝑆)| ≤ 𝛾) ≤

Bounds for Stochastic Block Models

Next, we present a nontrivial class of stochastic block models (SBMs) that satisfy the spectral gap condition required by Theorem 3.1. We begin with a formal definition of the SBM. Definition 3.3 (Stochastic Block Model [30, 40]). Let 𝑚 > 1 be the number of blocks, and suppose that the number of items 𝑛 is some integer multiple of 𝑚 such that 𝑛/𝑚 ≥ 2. Without loss of generality, let [𝑛] be partitioned into 𝑚 blocks, 𝐵 1 = {1, 2, . . . , 𝑛/𝑚}, 𝐵 2 = {𝑛/𝑚 + 1, . . . , 2𝑛/𝑚}, . . . , 𝐵𝑚 = {𝑛(𝑚−1)/𝑚+1, . . . , 𝑛}. Let 𝒒 = (𝑞 1, . . . , 𝑞𝑚 ) be the sampling probabilities for edges within each block, and let 𝑝 be the sampling probabilities for edges across blocks. Without loss of generality, assume that 𝑞 1 ≤ 𝑞 2 ≤ · · · ≤ 𝑞𝑚 , and suppose that 𝑞 1 > 𝑝 (i.e., the SBM is assortative). Then, a graph G = ( [𝑛], E) under the SBM(𝑛, 𝑚, 𝑝, 𝒒) model is generated by independently picking each edge (𝑖, 𝑗) with probability 𝑞𝑙 if 𝑖, 𝑗 ∈ 𝐵𝑙 for some 𝑙 ∈ [𝑚] and 𝑝 otherwise.

for sufficiently large 𝑛 with probability at least 1 − 𝑂 (𝑛 −5 ). Theorem 3.1 is proved in Section B.2. A proof sketch is available in Section 5.1. Some comments are due regarding each of the conditions that Theorem 3.1 requires, especially the variation condition (4) and spectral gap condition (5). First, (4) controls the asymptotic behavior of the ℓ 2 norm of 𝒒𝑖 = (𝑞𝑖1, . . . , 𝑞𝑖𝑛 ) with respect to its √ ℓ 1 norm, requiring that ∥𝒒𝑖 ∥ 2 /∥𝒒𝑖 ∥ 1 = Θ(1/ 𝑛) for all 𝑖 ∈ [𝑛]. Alternatively, one may obtain a geometric interpretation by noting that the angle between 1𝑛 (the all-ones vector) and 𝒒𝑖 is     1𝑛T 𝒒𝑖 ∥𝒒𝑖 ∥ 1 cos−1 = cos−1 √ , ∥1𝑛 ∥ 2 ∥𝒒𝑖 ∥ 2 𝑛∥𝒒𝑖 ∥ 2

It is clear from the definition that the stochastic block model is a valid semi-random graph model with base probability 𝑝. Note that when studying the asymptotics of the SBM, we will assume that 𝑚 (the number of blocks) is constant with respect to 𝑛, but 𝑝 and 𝒒 may depend on 𝑛. Using recent results by [40] on the spectra of SBM graphs, we can derive a counterpart of Corollary 3.2 for SBMs that satisfy a certain dynamic range condition.

thus (4) requires the angle between 1𝑛 and 𝒒𝑖 to be upper bounded √ by cos−1 (1/ 𝑠) for all 𝑖 ∈ [𝑛]. We argue that this condition is not excessively restrictive, as it allows for several useful models such as stochastic block models (see proof of Proposition 3.4). In fact, if √ 𝒒𝑖 is uniformly sampled√from [0, 1] 𝑛 , the quantity 𝑛∥𝒒𝑖 ∥ 2 /∥𝒒𝑖 ∥ 1 concentrates around 2/ 3 as 𝑛 → ∞. Thus, for sufficiently large 𝑛, most vectors 𝒒𝑖 ∈ [0, 1] 𝑛 satisfy (4) given 𝑠 > 4/3. The second condition, (5), requires the spectral gap of 𝑆, 1 − |𝜆2 (𝑆)| (recall that we order eigenvalues based on their absolute value in descending order), to be lower bounded by some constant with high probability. Such a requirement is expected because it is well established in the literature that BTL estimation critically depends on the spectral gap (or the effective resistance, a related

Proposition 3.4 (Error Bound for Stochastic Block Models). Suppose the observation graph G ∼ SBM(𝑛, 𝑚, 𝑝, 𝒒) with 𝑛𝑝 ≥ 𝑐 0 log5 (𝑛) and 𝑞𝑚 ≤ 𝑟𝑝 for some constants 𝑐 0, 𝑟 > 1. Then, there exists some constant 𝑐 1 > 0 such that the approximate score vector 𝝅ˆ estimated by the spectral method satisfies √︄ log(𝑛) ∥ 𝝅ˆ − 𝝅 ∥ ∞ ≤ 𝑐1 ∥𝝅 ∥ ∞ 𝑛𝑝𝑘 with high probability. 4

Entrywise Error Bounds for Spectral Ranking with Semi-Random Adversaries

Proof. Let 𝐴 be the adjacency matrix of G (i.e., 𝐴𝑖 𝑗 = 1{(𝑖, 𝑗) ∈ E}) and 𝐷 the degree matrix (i.e., 𝐷 = diag(𝒅 = (𝑑 1, . . . , 𝑑𝑛 )), where 𝑑𝑖 represents the degree of node 𝑖). First, we must show that the variation bound (4) is satisfied. For all 𝑙 ∈ [𝑚] and 𝑖 ∈ 𝐵𝑙 ,  2  ∑︁ 𝑛 𝑛 2 (𝑚 − 1) 2 𝑛 𝑞𝑖2𝑗 = − 𝑛 𝑞𝑙2 + 𝑝 𝑚 𝑚 𝑗:𝑗≠𝑖   2 𝑛 2 (𝑚 − 1) 2 2 𝑛 − 1 𝑞𝑙2 + 𝑝 ≤ 2𝑚 𝑚 𝑚2 !2 ∑︁ 𝑞𝑖 𝑗 , ≤ 2𝑚

guarantees that are robust against graphs with undesirable spectral properties. To this end, we examine a version of rank centrality with edge reweighting, taking inspiration from a line of work including [16, 34, 55] that studies how semi-random observations can be reweighted to more closely resemble a uniform sample which enjoys better guarantees.

4.1

The goal of the weighted rank centrality algorithm is to assign weights 𝑤𝑖 𝑗 ∈ [0, 1] to each edge of the observation graph such that the weighted graph G = ([𝑛], E, {𝑤𝑖 𝑗 }) has better spectral properties. The weights are symmetric (i.e., 𝑤 𝑗𝑖 = 𝑤𝑖 𝑗 ), and 𝑤𝑖 𝑗 = 0 for (𝑖, 𝑗) ∉ E. Let ∑︁ 𝑑 max ≜ max 𝑤𝑖 𝑗 ,

𝑗:𝑗≠𝑖

thus (4) holds with 𝑠 = 2𝑚 (recall that we assume 𝑚 to be a constant with respect to 𝑛). Next, we must control the spectral gap of 𝑆. From [40, Corollary 4.3], we have that 1 − |𝜆2 (𝐴rw )| ≥ 𝛾

𝑖 ∈ [𝑛]

𝑑 min ≜ min

𝑖 ∈ [𝑛]

𝑗:(𝑖,𝑗 ) ∈ E

∑︁

𝑤𝑖 𝑗 ,

𝑗:(𝑖,𝑗 ) ∈ E

denote the maximum and minimum weighted degree of G respectively, and let 𝑤 max ≤ 1 be the maximum edge weight. Next, we redefine the Markov matrix 𝑆 and its empirical counterpart 𝑆ˆ to incorporate these weights.

with high probability for some constant 𝛾 > 0, where 𝐴rw ≜ 𝐷 −1𝐴 refers to the simple random walk matrix of G, which is similar to the symmetric normalized adjacency matrix 𝐷 −1/2𝐴𝐷 −1/2 . Note that conditions (1.1) and (1.2) of [40] are always satisfied and the assortativity constant 𝜅 defined in [40, Equation (1.9)] is always positive due to our assumptions on 𝑝 and 𝒒. Í Since the stationary distribution of 𝐴rw is known to be 𝒅/ 𝑖 𝑑𝑖 , we can invoke a comparison theorem [47, Lemma 6] to relate the spectral gaps of 𝑆 and 𝐴rw . With high probability,

𝑝𝑖 𝑗 𝑤𝑖 𝑗   ,   𝑑 Í  𝑆𝑖 𝑗 ≜ 1 − 𝑑1 𝑙:(𝑖,𝑙 ) ∈ E 𝑝𝑖𝑙 𝑤𝑖𝑙 ,    0,  ˆ   𝑝𝑖 𝑗𝑑𝑤𝑖 𝑗 ,    Í 𝑆ˆ𝑖 𝑗 ≜ 1 − 𝑑1 𝑙:(𝑖,𝑙 ) ∈ E 𝑝ˆ𝑖𝑙 𝑤𝑖𝑙 ,    0, 

𝜋𝑖 𝑆 𝑖 𝑗 min (𝑖,𝑗 ) ∈ E 𝑑𝑖 𝐴𝑖rw 𝑗 1 − |𝜆2 (𝑆)| ≥ (1 − |𝜆2 (𝐴rw )|) 𝜋𝑖 max 𝑖 𝑑𝑖 𝜋𝑖 𝜋 𝑗 min 𝑑 min (𝑖,𝑗 ) ∈ E 𝜋𝑖 + 𝜋 𝑗 ≥ 𝛾 𝑑 max ∥𝝅 ∥ ∞ 𝑑 min 1 𝛾, ≥ 𝑑 max 2ℎ 2 which is a positive constant. Thus, all conditions of Theorem 3.1 are met, completing the proof. □

if (𝑖, 𝑗) ∈ E, if 𝑖 = 𝑗, otherwise, if (𝑖, 𝑗) ∈ E, if 𝑖 = 𝑗, otherwise,

where 𝑑 = 𝑑 max . Observe that the stationary distribution 𝜋 of 𝑆 remains unchanged and is given by (2). Similarly to the original rank centrality algorithm, the weighted rank centrality algorithm estimates the normalized score vector by computing the stationary ˆ distribution 𝜋ˆ of the weighted empirical Markov matrix 𝑆. Critical to the performance of this algorithm is the procedure in which the weights 𝑤𝑖 𝑗 are chosen. As a tool to analyze the effectiveness of the chosen weights, we define the weighted Laplacian matrix 𝐿𝑊 of G, ∑︁ 𝐿𝑤 ≜ 𝑤𝑖 𝑗 (𝒆𝑖 − 𝒆 𝑗 )(𝒆𝑖 − 𝒆 𝑗 ) T,

Note that the density requirement 𝑛𝑝 ≥ 𝑐 0 log5 (𝑛) is only needed so that the results of [40] can be applied to our regime, and is not necessarily a limitation of the algorithm. It is possible that Proposition 3.4 can be generalized to a broader class of SBMs, e.g., a regime where 𝑚 increases as a function of 𝑛, but we do not consider such cases for the sake of simplicity.

4

Weighted Algorithm Overview

(𝑖,𝑗 ) ∈ G,𝑖< 𝑗

where 𝒆𝑖 is the standard 𝑖th basis vector. The spectral gap of 𝐿𝑊 , 𝜆𝑛−1 (𝐿𝑊 ) =

Main Results on Weighted Spectral Method

𝒗 T 𝐿𝑊 𝒗 , 2 𝒗 ∈R𝑛 :𝒗 T 1𝑛 =0 ∥𝒗 ∥ 2 min

the second smallest eigenvalue of 𝐿𝑊 (also called the Fiedler value or algebraic connectivity), characterizes the spectral properties of the weighted graph. Note that 𝜆𝑛−1 (𝐿𝑊 ) only depends on the graph G and the set of weights 𝑤𝑖 𝑗 , not the underlying score vector 𝝅 or probabilities 𝑝𝑖 𝑗 .

Although our results in the previous section demonstrate that the standard spectral method remains effective in a broader range of settings beyond the Erdős-Rényi model, such as the important stochastic block model, no guarantees on performance can be made on graphs with vanishing spectral gaps. For example, an SBM that violates the dynamic range condition of Proposition 3.4 may have an asymptotically vanishing spectral gap (see, e.g., Section 6). In this section, we address this limitation and provide theoretical

4.2

Entry-Wise Error Bounds

In this section, we present the ℓ ∞ -error bounds for the weighted rank centrality algorithm. We begin by analyzing the general case 5

Lee, Makur, and Singh

for some constant 𝑐 0 > 1. Then, there exists some constants 𝑐 1, 𝑐 2, 𝑐 3 > 0 such that for all 𝑘 ≥ 10240ℎ 2 , the approximate score vector 𝝅ˆ estimated by the weighted spectral method with MMWU [55, Algorithm 2] satisfies √︄ √︄ log(𝑛) 𝑛 log(𝑛) ∥ 𝝅ˆ − 𝝅 ∥ ∞ ≤ 𝑐1 + 𝑐2 ∥𝝅 ∥ ∞ 𝑛𝑝𝑘 (𝑛𝑝) 3𝑘

for any arbitrary set of weights, then discuss a method to effectively choose these weights in order to guarantee good performance against a semi-random adversary. First, we derive the following error bound for a deterministic observation graph that holds for any given set of weights. Theorem 4.1 (Error Bounds for Generic Weighted Rank Centrality). Suppose that the weighted observation graph G = ([𝑛], E, {𝑤𝑖 𝑗 }) is connected. Assume that 𝑑 min ≥ 1, 𝑑 max ≤ 2𝑛𝑝 for some 𝑝, and 𝑘 ≥ 640ℎ 2𝑛 log(𝑛)𝑝/𝜆𝑛−1 (𝐿𝑊 ) 2 . Then, there exists constants 𝑐 1, 𝑐 2, 𝑐 3 > 0 such that the approximate score vector 𝝅ˆ generated by the weighted spectral method satisfies √︂ 𝑛 log(𝑛)𝑝 ∥ 𝝅ˆ − 𝝅 ∥ ∞ 𝑐1 ≤ ∥𝝅 ∥ ∞ 𝑘 𝜆𝑛−1 (𝐿𝑊 ) √︂ 𝑛 2 log(𝑛)𝑝 2 𝑐2 + 𝑊 2 𝑘 𝜆𝑛−1 (𝐿 ) ! √︂ 𝑛 4 log(𝑛)𝑝 3 𝑐3 + 𝑘 𝜆𝑛−1 (𝐿𝑊 ) 3

Corollary 4.3 (Error Bounds for MMWU-Weighted Spectral Method on Dense Graphs). In addition to the assumptions √ of Theorem 4.2, suppose that 𝑛𝑝 ≥ 𝑐 𝑛 for some constant 𝑐 > 0. Then, the error bound simplifies to √︄ log(𝑛) ∥ 𝝅ˆ − 𝝅 ∥ ∞ ≤𝐶 ∥𝝅 ∥ ∞ 𝑛𝑝𝑘

with probability at least 1 − 𝑂 (𝑛 −5 ).

with high probability for some constant 𝐶 > 0.

Theorem 4.1 is proved in Section C. A proof sketch is provided in Section 5.2. Note that the error bounds depend almost entirely on the spectral properties of G, namely 𝜆𝑛−1 (𝐿𝑊 ). In particular, one can recover a result similar to Corollary 3.2 from this theorem by observing that unweighted Erdős-Rényi graphs satisfy 𝜆𝑛−1 (𝐿𝑊 ) ≥ 𝑛𝑝/2 (and the 𝑑 min and 𝑑 max constraints) with high probability (see [55, Lemma 10]). Thus, as long as we can find an appropriate set of weights such that 𝜆𝑛−1 (𝐿𝑊 ) grows like 𝑛𝑝 (i.e., so that G “behaves like” an Erdős-Rényi graph spectrally), we can achieve “Erdős-Rényi-like” performance for a larger class of graphs, such as semi-randomly generated graphs. To show that such a set of weights must exist, we can utilize a monotone coupling argument (see Lemma 5.3) to show that any property that holds with high probability for Erdős-Rényi graphs can also be recovered with high probability from a well-chosen subgraph of a semi-randomly generated graph. Furthermore, given any subgraph G ′ = ([𝑛], E ′ ) of G, we can choose weights ( 1, (𝑖, 𝑗) ∈ E ′, 𝑤𝑖 𝑗 = 0, otherwise

Thus, the MMWU-weighted spectral method is asymptotically optimal for sufficiently dense graphs. Note that it is still possible for the spectral gap to decay towards zero even in such dense regimes. We emphasize that this theoretical result does not imply that the weighted spectral method is unviable for sparse semirandom graphs, but only that optimal bounds in such settings is yet unavailable. It is possible that alternate proof techniques may allow optimal bounds to be obtained for sparser regimes. We believe this to be a promising direction for future work.

with probability at least 1 − 𝑂 (𝑛 −5 ). Theorem 4.2 follows from Theorem 4.1 and [55, Theorem 10]. Note that the bound in Theorem 4.2 can be simplified when the graph is sufficiently dense, as the following corollary demonstrates.

5

Analysis and Proof Sketches for Main Results

In this section, we present brief proof sketches for each of our main results and state some necessary lemmas.

5.1

Proof Sketch of Theorem 3.1

Before the entry-wise error of the unweighted spectral method can be bounded, a tight bound on the ℓ 2 error is needed. Lemma 5.1 (ℓ 2 Error Bounds for Unweighted Spectral Method [14, Theorem 5.2]). Under the setting of Theorem 3.1, with probability at least 1 − 𝑂 (𝑛 −10 ), we have

so that the weighted graph is equivalent to G ′ . This implies that there must exist a set of weights such that the weighted graph satisfies 𝜆𝑛−1 (𝐿𝑊 ) ≥ 𝑛𝑝/2 with high probability. Thus, the problem reduces to finding the weights (under the 𝑑 min and 𝑑 max constraints) that maximize 𝜆𝑛−1 (𝐿𝑊 ). As [55] showed, this optimization problem can be formulated as a semi-definite program (SDP) approximately solvable in nearlinear time with the Matrix Multiplicative Weight Update (MMWU) algorithm [55, Algorithm 2]. Since the MMWU method can 1/2approximate the optimization problem in near-linear time, we can obtain the following guarantee for the MMWU-weighted spectral method.

∥ 𝝅ˆ − 𝝅 ∥ 2 𝑐3 ≤ √︁ ∥𝝅 ∥ 2 𝛾 𝑛𝑝𝑘 for some constant 𝑐 3 . Lemma 5.1 is proved in Section B.1. Note that simply using Lemma 5.1 in combination with the norm inequality ∥ · ∥ ∞ ≤ ∥ · ∥ 2 ≤ √ 𝑛∥ · ∥ ∞ is not sufficient to obtain the tight bound of Theorem 3.1. In order to obtain a tight bound, we decompose the entry-wise error to multiple components and make extensive use of concentration inequalities such as Hoeffding’s inequality and Bernstein’s inequality [7] to bound the deviation of each component from the mean with high probability. A key component is the celebrated leave-one-out argument introduced by [14], which isolates the randomness of a single node to simplify analysis. Although the general

Theorem 4.2 (Error Bounds for MMWU-Weighted Spectral Method). Assume that the observation graph is generated by a semirandom adversary with base probability 𝑝 satisfying 𝑛𝑝 ≥ 𝑐 0 log(𝑛) 6

Entrywise Error Bounds for Spectral Ranking with Semi-Random Adversaries

flavor of our proof follows [14], the heterogeneity of our semirandom setting presents unique challenges, as our edges are not identically distributed. At a high level, our proof decomposes the error term into  Í Í 1 (−𝑖 ) 𝜋ˆ𝑖 − 𝜋𝑖 = Í ) 𝑗 (𝑝ˆ 𝑗𝑖 𝜋 𝑗 − 𝑝ˆ𝑖 𝑗 𝜋𝑖 ) + 𝑗 𝑝ˆ 𝑗𝑖 ( 𝜋ˆ 𝑗 − 𝜋ˆ 𝑗 ˆ 𝑗 𝑝𝑖 𝑗  Í Í + 𝑗 𝑝ˆ 𝑗𝑖 ( 𝜋ˆ 𝑗(−𝑖 ) − 𝜋¯ 𝑗(−𝑖 ) ) + 𝑗 𝑝ˆ 𝑗𝑖 ( 𝜋¯ 𝑗(−𝑖 ) − 𝜋 𝑗 ) , (6)

is possible to probabilistically choose an Erdős-Rényi subgraph of G according to P(𝐺 E | 𝐺 S = GS ). Critically, this allows us to show that any useful property of Erdős-Rényi graphs can be recovered by a carefully chosen subgraph of a semi-randomly generated graph, as the following lemma shows.

where the leave-one-out vector 𝝅ˆ (−𝑖 ) is defined as the stationary distribution of the leave-one-out stochastic matrix 𝑝ˆ𝑖 𝑗   if 𝑖 ≠ 𝑚 and 𝑗 ≠ 𝑚 and 𝑖 ≠ 𝑗 𝑆ˆ𝑖 𝑗 = 𝑑 ,   𝑝 𝑞 (−𝑚) 𝑖 𝑗 𝑖 𝑗 (𝑆ˆ )𝑖 𝑗 ≜ , if (𝑖 = 𝑚 or 𝑗 = 𝑚) and 𝑖 ≠ 𝑗, 𝑑    1 − Í (𝑆ˆ (−𝑚) ) , if 𝑖 = 𝑗, 𝑖𝑙 𝑙:𝑙≠𝑖 

P𝐺 E ∼ER(𝑛,𝑝 ) (𝐺 E ∈ P) ≥ 1 − 𝑂 (𝑛 −𝑡 )

Lemma 5.3 (Recovering Properties of Erdős-Rényi graphs from Subgraphs of Semi-Random Graphs). Let P be some graph property that holds for an Erdős-Rényi graph (with edge sampling probability 𝑝) with high probability, i.e.,

for some fixed 𝑡 > 0. Let 𝐺 S be a semi-randomly generated graph under edge sampling probabilities {𝑞𝑖 𝑗 }. Then, with high probability, there must exist a subgraph of 𝐺 S that satisfies P, i.e., P𝐺 S ∼SR(𝑛,{𝑞𝑖 𝑗 } ) (∃G ⊆ 𝐺 S : G ∈ P) ≥ 1 − 𝑂 (𝑛 −𝑡 ).

and 𝝅¯ (−𝑖 ) is defined as 𝜋¯𝑖(−𝑚) ≜

Í

Proof. Given a graph GS , let 𝐺 E be distributed according to P(𝐺 E | 𝐺 S = GS ) under the coupling defined in Definition 5.2. Note that P(𝐺 E ⊆ GS ) = 1 by definition. Then,

𝑗∉{𝑖,𝑚} 𝑝ˆ 𝑗𝑖 𝜋 𝑗 + 𝑝𝑚𝑖 𝑞𝑚𝑖 𝜋𝑚

Í

𝑗∉{𝑖,𝑚} 𝑝ˆ𝑖 𝑗 + 𝑝𝑖𝑚 𝑞𝑖𝑚

.

Each of the boxed terms in (6) are bounded separately, allowing each source of error to be isolated. Finally, the terms, each bounded with high probability, are combined with a union bound to obtain the final bound with the desired probability.

5.2

P𝐺 E |𝐺 S (𝐺 E ∈ P | 𝐺 S = GS ) ≤ 1{∃G ⊆ GS : G ∈ P}. Thus, P𝐺 S ∼SR(𝑛,{𝑞𝑖 𝑗 } ) (∃G ⊆ 𝐺 S : G ∈ P) = E𝐺 S ∼SR(𝑛,{𝑞𝑖 𝑗 } ) [1{∃G ⊆ 𝐺 S : G ∈ P}]

Proof Sketch of Theorem 4.1

≥ E𝐺 S ∼SR(𝑛,{𝑞𝑖 𝑗 } ) [P𝐺 E |𝐺 S (𝐺 E ∈ P | 𝐺 S )]

Similarly to the proof of Theorem 3.1, the entry-wise error is decomposed into multiple components that are bounded separately. However, the flavor of analysis is significantly different because the graph is fixed. In particular, we make use of various results on graph Laplacian spectra such as [55, Lemma 18] and matrix concentration inequalities [54] to characterize the relationship between error terms and Laplacian eigenvalues. In addition, we use ideas from, e.g., [22] to recursively bound the ℓ 2 and ℓ ∞ norms of various error terms to obtain a tight bound.

5.3

= P𝐺 E ∼ER(𝑛,𝑝 ) (𝐺 E ∈ P) ≥ 1 − 𝑂 (𝑛 −𝑡 ), which completes the proof.

□

Although this lemma establishes the existence of an appropriate subgraph with high probability, it does not provide an explicit method to recover one. Indeed, it is not trivial to recover an ErdősRényi subgraph from a semi-randomly generated graph, especially if the underlying edge sampling probabilities are unknown. Thankfully, the mere existence of a valid subgraph is sufficient to obtain results such as Theorem 4.2.

Analysis of Theorem 4.2

In order to obtain results such as Theorem 4.2, it is essential to formally characterize the relationship between an Erdős-Rényi graph and a semi-randomly generated graph with the same 𝑝 by defining a coupling between the two random variables.

6

Experiments

In this section, we conduct two numerical experiments to complement our theoretical results. The purpose of the experiments is to highlight a setting where reweighting is beneficial, and another where it is not. In each experiment, we compare the performance of the unweighted and MMWU-weighted spectral methods on random graphs of various sizes. To reduce the effect of randomness, we run each experiment 25 times and take the median. The algorithms were implemented on Python, and the greedy 1/2-approximation oracle described in [55, Theorem 5] was used to implement the MMWU algorithm. Experiment 1. In the first experiment (Figure 2(a)–(c)), graphs are generated from a stochastic block model. Although we only considered SBMs with a single inter-block probability in our theoretical exposition in Section 3.2, we will use the more general definition of a stochastic block model here, where the edge probabilities between pairs of blocks are given as an arbitrary symmetric matrix. The 3-block SBM used in this experiment has block edge sampling probabilities given by the matrix

Definition 5.2 (Monotone Coupling Between Erdős-Rényi Graphs and Semi-Random Graphs). Given 𝑛 ∈ N, 𝑝 ∈ (0, 1], and {𝑞𝑖 𝑗 ∈ [𝑝, 1] | ∀𝑖, 𝑗 ∈ N : 𝑖 < 𝑗 ≤ 𝑛}, for each pair (𝑖, 𝑗) ∈ [𝑛] 2 such that 𝑖 < 𝑗, draw an independent uniformly distributed random variable 𝑈𝑖 𝑗 ∼ Unif(0, 1). Construct two graphs, GE = ([𝑛], EE ) and GS = ( [𝑛], ES ), such that (𝑖, 𝑗) ∈ EE if and only if 𝑈𝑖 𝑗 ≤ 𝑝 and (𝑖, 𝑗) ∈ ES if and only if 𝑈𝑖 𝑗 ≤ 𝑞𝑖 𝑗 . The graphs GE and GS are realizations of the monotone coupling between the random variables 𝐺 E , which is distributed according to the Erdős-Rényi model with edge sampling probability 𝑝, and 𝐺 S , which is distributed according to the semi-random model with edge sampling probabilities {𝑞𝑖 𝑗 }. Furthermore, P(𝐺 E ⊆ 𝐺 S ) = 1. Under this coupling, the edge set of the semi-randomly generated graph GS is always a superset of the edge set of GE . This implies that given a realization of a semi-randomly generated graph GS , it 7

Lee, Makur, and Singh

0.07

5.2 × 10 1

0.06

5.1 × 10 1 Error

0.05 0.04 0.03 0.02 0.01

Unweighted Weighted (MMWU) 40

60

80 100 Number of items (n)

Estimation Error (Median)

5.3 × 10 1

Rel

Spectral Gap

Spectral Gap (Median)

Unweighted Weighted (MMWU)

5 × 10 1

(a) Spectral gaps (1 − |𝜆2 (𝑆 ) |) of the unweighted and MMWU-weighted canonical Markov matrices as a function of 𝑛 (Experiment 1).

4.8 × 10 1

80

4.7 × 10 1

100

40

80 100 Number of items (n)

120

140

Estimation Error (Median) 4.175 × 10 1

0.09

0.4

0.2

0

20

40

60

80

100

120

Error

0.07 0.06

Weights (n=135)

1.0

20

0.8

40

4.1 × 10 1

60

4.075 × 10 1

80

4.05 × 10 1

100

4.025 × 10 1 40

60

80 100 Number of items (n)

120

140

(d) Spectral gaps (1 − |𝜆2 (𝑆 ) |) of the unweighted and MMWU-weighted canonical Markov matrices as a function of 𝑛 (Experiment 2).

0.0

(c) Visualization of the MMWU-computed weights in Experiment 1 (𝑛 = 135).

0

Unweighted Weighted (MMWU)

4.125 × 10 1

0.08

0.05

0.6

4.15 × 10 1

Rel

Spectral Gap

60

(b) Relative ℓ ∞ -error ( ∥ 𝝅ˆ∥𝝅−𝝅∥ ∞∥ ∞ ) of the unweighted and MMWU-weighted spectral method with respect to 𝑛 (Experiment 1).

Unweighted Weighted (MMWU)

0.8

120

Spectral Gap (Median) 0.10

20

60

4.9 × 10 1

140

1.0

40

4.6 × 10 1 120

Weights (n=135)

0

0.6

0.4

0.2

120 40

60

80 100 Number of items (n)

120

140

(e) Relative ℓ ∞ -error ( ∥ 𝝅ˆ∥𝝅−𝝅∥ ∞∥ ∞ ) of the unweighted and MMWU-weighted spectral method with respect to 𝑛 (Experiment 2).

0

20

40

60

80

100

120

0.0

(f) Visualization of the MMWU-computed weights in Experiment 2 (𝑛 = 135).

Figure 2: Experiment 1 (Subfigures (a)–(c)): 3-block SBM with edge sampling probabilities between each pair of blocks given by the matrix (7). Experiment 2 (Subfigures (d)–(f)): Erdős-Rényi model with edge sampling probability 𝑝 = 2 log(𝑛)/𝑛. to zero as 𝑛 increases in this model. MMWU reweighting counteracts this decrease to keep the spectral gap relatively constant with respect to 𝑛. Figure 2(b) plots the relative entry-wise error of the unweighted and weighted spectral methods on this model as a function of 𝑛. As the plot shows, the MMWU-weighted spectral method outperforms the standard spectral method, especially as 𝑛 increases. Figure 2(c), a heatmap of the edge weights assigned by the MMWU algorithm, gives us a glimpse into the inner workings of the reweighting process. Regions that are overrepresented (the top left corner) are assigned smaller weights, while samples that are underrepresented are given higher precedence. Experiment 2. On the other hand, the second experiment (Figure 2(d)–(f)) serves as an example of a regime where reweighting is relatively unnecessary. In this experiment, the graph is generated from an Erdős-Rényi model with edge sampling probability 𝑝 = 2 log(𝑛)/𝑛 (with 𝑛 taking the same values as before). Since Erdős-Rényi graphs are known to have good spectral properties, the benefit of reweighting is relatively minor. Interestingly, as Figure 2(d) shows, the MMWU method is still effective in increasing the spectral gap of the stochastic matrix,

1 1 0    log(𝑛)  log(𝑛) 2 𝑛 , 𝑃 = 1 2 𝑛 (7)  log(𝑛)  0 2 log(𝑛)  2 𝑛 𝑛   where 𝑛 ∈ {30, 45, 60, 75, 90, 105, 120, 135} is the number of items (note that we choose multiples of 3 to ensure that each block has the same size). Note that this SBM is a valid semi-random model (albeit with 𝑝 = 0), but does not satisfy the assumptions of our main theoretical results. Of course, as the simulation results show, this does not preclude the MMWU-weighted spectral method from being effective. The setting of Experiment 1 has several properties that make reweighting especially worthwhile. For example, the node degrees exhibit large variation. While nodes in the first block each have degree Θ(𝑛), the average degree of nodes in the third block is only Θ(log(𝑛)). Thus, the ratio 𝑑 max /𝑑 min is not bounded as 𝑛 increases. In such settings, reweighting is beneficial because it effectively normalizes node degrees, improving the spectral properties of the stochastic matrix significantly. In addition, as Figure 2(a) shows, the spectral gap of the unweighted canonical Markov matrix decays 8

Entrywise Error Bounds for Spectral Ranking with Semi-Random Adversaries

even though the unweighted spectral gap is already well controlled. However, this increase in spectral gap does not translate to improved performance, as Figure 2(e) illustrates. Since the purpose of the reweighting is to recover Erdős-Rényi-like properties, it is expected that it is not of much use if the initial graph is already generated from an Erdős-Rényi model. Furthermore, Figure 2(f) demonstrates, the weights chosen by the MMWU algorithm in this setting are mostly evenly distributed, unlike Figure 2(c). Still, even in this “worst case” setting, the weighted spectral method still holds its ground against the unweighted version.

[19] Ronen Eldan, Miklós Z Rácz, and Tselil Schramm. 2017. Braess’s paradox for the spectral gap in random graphs and delocalization of eigenvectors. Random Structures & Algorithms 50, 4 (July 2017), 584–611. [20] Arpad E. Elo. 1978. The Rating of Chess Players, Past and Present. Arco, New York, NY, USA. [21] Jianqing Fan, Zhipeng Lou, Weichen Wang, and Mengxin Yu. 2025. Ranking inferences based on the top choice of multiway comparisons. J. Amer. Statist. Assoc. 120, 549 (March 2025), 237–250. [22] Jianqing Fan, Zhipeng Lou, Weichen Wang, and Mengxin Yu. 2026. Spectral Ranking Inferences based on General Multiway Comparisons. Operations Research 74, 1 (January–February 2026), 161–180. [23] Uriel Feige and Joe Kilian. 2001. Heuristics for semirandom graph problems. J. Comput. System Sci. 63, 4 (December 2001), 639–671. [24] Miroslav Fiedler. 1973. Algebraic connectivity of graphs. Czechoslovak Mathematical Journal 23, 2 (1973), 298–305. [25] L. R. Ford. 1957. Solution of a Ranking Problem from Binary Comparisons. The American Mathematical Monthly 64, 8 Part 2 (October 1957), 28–33. [26] Chao Gao, Yandi Shen, and Anderson Y. Zhang. 2023. Uncertainty quantification in the Bradley-Terry-Luce model. Information and Inference 12, 2 (June 2023), 1073–1140. [27] Xing Gao and Yu Cheng. 2023. Robust matrix sensing in the semi-random model. In Proceedings of the Advances in Neural Information Processing Systems 36 (NeurIPS). New Orleans, LA, USA, 63385–63408. [28] John Guiver and Edward Snelson. 2009. Bayesian inference for Plackett-Luce ranking models. In Proceedings of the 26th Annual International Conference on Machine Learning (ICML). Montreal, QC, Canada, 377–384. [29] Julien Hendrickx, Alex Olshevsky, and Venkatesh Saligrama. 2020. Minimax Rate for Learning From Pairwise Comparisons in the BTL Model. In Proceedings of the 37th Annual International Conference on Machine Learning (ICML), Vol. 119. Vienna, Austria, 4193–4202. [30] Paul W. Holland, Kathryn Blackmond Laskey, and Samuel Leinhardt. 1983. Stochastic blockmodels: First steps. Social Networks 5, 2 (June 1983), 109–137. [31] David R. Hunter. 2004. MM Algorithms for Generalized Bradley-Terry Models. The Annals of Statistics 32, 1 (February 2004), 384–406. [32] Ali Jadbabaie, Anuran Makur, and Devavrat Shah. 2020. Estimation of Skill Distribution from a Tournament. In Proceedings of the Advances in Neural Information Processing Systems 33 (NeurIPS). Vancouver, BC, Canada, 8418–8429. [33] Ali Jadbabaie, Anuran Makur, and Devavrat Shah. 2024. Estimation of skill distributions. IEEE Transactions on Information Theory 70, 9 (September 2024), 6447–6480. [34] Arun Jambulapati, Jerry Li, Christopher Musco, Aaron Sidford, and Kevin Tian. 2021. Fast and Near-Optimal Diagonal Preconditioning. (November 2021). arXiv:2008.01722v2 [math.OC]. [35] Minje Jang, Sunghyun Kim, and Changho Suh. 2018. Top-𝐾 rank aggregation from 𝑀 -wise comparisons. IEEE Journal of Selected Topics in Signal Processing 12, 5 (May 2018), 989–1004. [36] Jonathan Kelner, Jerry Li, Allen X Liu, Aaron Sidford, and Kevin Tian. 2023. Semirandom sparse recovery in nearly-linear time. In Proceedings of the Thirty Sixth Annual Conference on Learning Theory (COLT). Bangalore, India, 2352–2398. [37] David A. Levin, Yuval Peres, and Elizabeth L. Wilmer. 2009. Markov Chains and Mixing Times (first ed.). American Mathematical Society. [38] Wanshan Li, Shamindra Shrotriya, and Alessandro Rinaldo. 2022. ℓ∞ -Bounds of the MLE in the BTL Model under General Comparison Graphs. In Proceedings of the Thirty-Eighth Conference on Uncertainty in Artificial Intelligence. Eindhoven, The Netherlands, 1178–1187. [39] Yue Liu, Ethan X. Fang, and Junwei Lu. 2023. Lagrangian inference for ranking problems. Operations Research 71, 1 (January–February 2023), 202–223. [40] Matthias Löwe and Sara Terveer. 2025. Spectral properties of the stochastic block model and their application to hitting times of random walks. (April 2025). https://arxiv.org/abs/2401.07896v3 arXiv:2401.07896v3 [math.PR]. [41] Robert Duncan Luce. 1959. Individual Choice Behavior: A Theoretical Analysis. John Wiley & Sons Inc., New York, NY, USA. [42] Konstantin Makarychev, Yury Makarychev, and Aravindan Vijayaraghavan. 2012. Approximation algorithms for semi-random partitioning problems. In Proceedings of the Forty-Fourth Annual ACM Symposium on Theory of Computing. New York, NY, USA, 367–384. [43] Anuran Makur and Japneet Singh. 2025. Hypothesis Testing for Generalized Thurstone Models. In Proceedings of the 42nd International Conference on Machine Learning (ICML). Vancouver, BC, Canada, 42730–42764. [44] Anuran Makur and Japneet Singh. 2025. Minimax Hypothesis Testing for the Bradley–Terry–Luce Model. IEEE Transactions on Information Theory 71, 12 (December 2025), 9163–9202. [45] Kenneth Massey. 1997. Statistical models applied to the rating of sports teams. (1997). Bluefield College. [46] J. N. S. Matthews and K. P. Morris. 1995. An Application of Bradley-Terry-Type Models to the Measurement of Pain. Journal of the Royal Statistical Society Series C (Applied Statistics) 44, 2 (1995), 243–255.

Acknowledgments This work is supported in part by the National Science Foundation (NSF) CAREER Award under Grant CCF-2337808.

References [1] Eldridge S Adams. 2005. Bayesian analysis of linear dominance hierarchies. Animal Behaviour 69, 5 (May 2005), 1191–1201. [2] Julian Asilis, Xi Chen, Dutch Hansen, and Shang-Hua Teng. 2026. Semi-Random Graphs, Robust Asymmetry, and Reconstruction. In Proceedings of the 17th Innovations in Theoretical Computer Science Conference (ITCS). Milan, Italy, 12:1–12:21. [3] Linas Baltrunas, Tadas Makcinskas, and Francesco Ricci. 2010. Group recommendations with rank aggregation and collaborative filtering. In Proceedings of the Fourth ACM Conference on Recommender Systems. Barcelona, Spain, 119––126. [4] Daniel Barry and JA Hartigan. 1993. Choice models for predicting divisional winners in major league baseball. J. Amer. Statist. Assoc. 88, 423 (1993), 766–774. [5] Avrim Blum and Joel Spencer. 1995. Coloring random and semi-random 𝑘 colorable graphs. Journal of Algorithms 19, 2 (November 1995), 204–234. [6] Heejong Bong, Wanshan Li, Shamindra Shrotriya, and Alessandro Rinaldo. 2020. Nonparametric estimation in the dynamic Bradley-Terry model. In Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics (AISTATS). 3317–3326. [7] Stéphane Boucheron, Gábor Lugosi, and Olivier Bousquet. 2004. Concentration Inequalities. In Advanced Lectures on Machine Learning, Olivier Bousquet, Ulrike von Luxburg, and Gunnar Rätsch (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg, 208–240. [8] Ralph Allan Bradley and Milton E. Terry. 1952. Rank Analysis of Incomplete Block Designs. I. The Method of Paired Comparisons. Biometrika 39, 3/4 (December 1952), 324–345. [9] François Caron and Arnaud Doucet. 2012. Efficient Bayesian Inference for Generalized Bradley-Terry Models. Journal of Computational and Graphical Statistics 21, 1 (March 2012), 174–196. [10] Manuela Cattelan, Cristiano Varin, and David Firth. 2013. Dynamic BradleyTerry modelling of sports tournaments. Journal of the Royal Statistical Society: Series C (Applied Statistics) 62, 1 (January 2013), 135–150. [11] Sourav Chatterjee. 2015. Matrix Estimation by Universal Singular Value Thresholding. The Annals of Statistics 43, 1 (February 2015), 177–214. [12] Pinhan Chen, Chao Gao, and Anderson Y Zhang. 2022. Partial recovery for top-𝑘 ranking: optimality of MLE and suboptimality of the spectral method. The Annals of Statistics 50, 3 (June 2022), 1618–1652. [13] Yanxi Chen. 2023. Ranking from Pairwise Comparisons in General Graphs and Graphs with Locality. (April 2023). https://arxiv.org/abs/2304.06821 arXiv:2304.06821 [stat.ML]. [14] Yuxin Chen, Jianqing Fan, Cong Ma, and Kaizheng Wang. 2019. Spectral Method and Regularized MLE are both Optimal for Top-𝐾 Ranking. The Annals of Statistics 47, 4 (2019), 2204–2235. [15] Yuxin Chen and Changho Suh. 2015. Spectral MLE: Top-𝑘 rank aggregation from pairwise comparisons. In Proceedings of the 32nd International Conference on Machine Learning. Lille, France, 371–380. [16] Yu Cheng and Rong Ge. 2018. Non-convex matrix completion against a semirandom adversary. In Proceedings of the 31st Conference On Learning Theory (COLT). Stockholm, Sweden, 1362–1394. [17] Wei-Lin Chiang, Lianmin Zheng, Ying Sheng, Anastasios Nikolas Angelopoulos, Tianle Li, Dacheng Li, Banghua Zhu, Hao Zhang, Michael Jordan, Joseph E. Gonzalez, and Ion Stoica. 2024. Chatbot Arena: An Open Platform for Evaluating LLMs by Human Preference. In Proceedings of the 41st International Conference on Machine Learning (ICML). Vienna, Austria, 8359–8388. [18] Paul F Christiano, Jan Leike, Tom Brown, Miljan Martic, Shane Legg, and Dario Amodei. 2017. Deep reinforcement learning from human preferences. In Proceedings in the Advances of Neural Information Processing Systems 30 (NIPS). Long Beach, CA, USA, 4299–4307. 9

Lee, Makur, and Singh

Next, we upper bound a . Following the proof of [14, Theorem 5.2], we have √︂ √︂ ℎ T 1 ∥𝝅 ∥ 2 ˆ 2 ≲ a ≤ ∥𝝅 (𝑆 − 𝑆)∥ . √︁ 𝑛 𝑛 𝑛𝑝𝑘 −10

[47] Sahand Negahban, Sewoong Oh, and Devavrat Shah. 2017. Rank Centrality: Ranking from Pairwise Comparisons. Operations Research 65, 1 (January–February 2017), 266–287. [48] Long Ouyang, Jeffrey Wu, Xu Jiang, Diogo Almeida, Carroll Wainwright, Pamela Mishkin, Chong Zhang, Sandhini Agarwal, Katarina Slama, Alex Ray, John Schulman, Jacob Hilton, Fraser Kelton, Luke Miller, Maddie Simens, Amanda Askell, Peter Welinder, Paul F Christiano, Jan Leike, and Ryan Lowe. 2022. Training language models to follow instructions with human feedback. In Proceedings in the Advances in Neural Information Processing Systems 35 (NeurIPS). New Orleans, LA, USA, 27730–27744. [49] Lawrence Page, Sergey Brin, Rajeev Motwani, and Terry Winograd. 1999. The PageRank Citation Ranking: Bringing Order to the Web. Technical Report 1999-66. Stanford InfoLab. [50] Robin L. Plackett. 1975. The Analysis of Permutations. Journal of the Royal Statistical Society, Series C (Applied Statistics) 24, 2 (1975), 193–202. [51] Nihar B. Shah, Sivaraman Balakrishnan, Joseph Bradley, Abhay Parekh, Kannan Ramchandran, and Martin J. Wainwright. 2016. Estimation from Pairwise Comparisons: Sharp Minimax Bounds with Topology Dependence. Journal of Machine Learning Research 17, 58 (2016), 1–47. [52] Gordon Simons and Yi-Ching Yao. 1999. Asymptotics when the number of parameters tends to infinity in the Bradley-Terry model for paired comparisons. The Annals of Statistics 27, 3 (June 1999), 1041–1060. [53] Stephen M. Stigler. 1994. Citation Patterns in the Journals of Statistics and Probability. Statist. Sci. 9, 1 (February 1994), 94–108. [54] Joel A Tropp. 2015. An introduction to matrix concentration inequalities. Foundations and Trends in Machine Learning 8, 1-2 (May 2015), 1–230. [55] Yuepeng Yang, Antares Chen, Lorenzo Orecchia, and Cong Ma. 2024. Top𝐾 ranking with a monotone adversary. In Proceedings of the Thirty Seventh Conference on Learning Theory (COLT), Shipra Agrawal and Aaron Roth (Eds.). Edmonton, AB, Canada, 5123–5162. [56] Ernst Zermelo. 1929. Die Berechnung der Turnier-Ergebnisse als ein Maximumproblem der Wahrscheinlichkeitsrechnung. Mathematische Zeitschrift 29, 1 (December 1929), 436–460.

A

1−𝑂 (𝑛

)

Combining the bounds, we have ∥𝝅 − 𝝅ˆ ∥ 2 ∥𝝅 ∥ 2

1 , √︁ 𝛾 𝑛𝑝𝑘 1−𝑂 (𝑛 −10 ) ≲

completing the proof.

B.2

□

Proof of Theorem 3.1

Now we are ready to prove Theorem 3.1. Proof. Before we begin, we will first condition on the event that 1 − 𝜆2 (𝑆) ≥ 𝛾, which by assumption has probability at least 1 − 𝑛 −5 . First, let 𝐴 be the adjacency matrix of the observed G. In particular, this implies that E[𝐴𝑖 𝑗 ] = 𝑞𝑖 𝑗 and E[𝑝ˆ𝑖 𝑗 | 𝐴𝑖 𝑗 = 𝑎] = 𝑝𝑖 𝑗 𝑎, ∀𝑎 ∈ {0, 1}. We will use the shorthands P(· | 𝐴) and E[· | 𝐴] to refer to probabilities and expectations conditioned on 𝐴. We also define ∑︁ 𝑑𝑖 ≜ 𝐴𝑖 𝑗

Introduction to Appendices

𝑗

In the appendices, we prove the various theorems and propositions introduced in the body. We use the shorthand

to be the degree of node 𝑖. Since each 𝐴𝑖 𝑗 ∼ Bernoulli(𝑞𝑖 𝑗 ), using a Chernoff bound, we have !   Í ∑︁ 1 ∑︁ 𝑗 𝑞𝑖 𝑗 P 𝑑𝑖 − 𝑞𝑖 𝑗 ≥ 𝑞𝑖 𝑗 ≤ 2 exp − 2 𝑗 12 𝑗   (𝑛 − 1)𝑝 ≤ 2 exp − 12  𝑐  0 ≤ 3 exp − log(𝑛) 12 ≤ 3𝑛 −10

𝑎 ≥ 𝑏 1−𝑂 (𝑛 −𝑡 )

to say “𝑎 ≥ 𝑏 with probability at least 1 − 𝑂 (𝑛 −𝑡 )”.

B Proofs on Unweighted Spectral Method B.1 Proof of Lemma 5.1 First, we prove Lemma 5.1.

since 𝑐 0 ≥ 120. In particular, since all 𝑞𝑖 𝑗 ≥ 𝑝, we have 𝑑𝑖 ≥ 𝑛𝑝/2 ≥ 𝑐 0 log(𝑛)/2 with high probability. Next, recall that since 𝝅ˆ is the ˆ we have stationary distribution of 𝑆, Í 𝑗 𝑝ˆ 𝑗𝑖 𝜋ˆ 𝑗 . 𝜋ˆ𝑖 = Í 𝑗 𝑝ˆ𝑖 𝑗

Proof. We begin by invoking [14, Theorem 5.1] to get √ ∥𝝅 − 𝝅ˆ ∥ 2 ≤ 𝑛ℎ∥𝝅 − 𝝅ˆ ∥ 𝝅 ≤

√ ˆ 𝝅 𝑛ℎ ∥𝝅 T (𝑆 − 𝑆)∥ 1 − |𝜆2 (𝑆)| − ∥𝑆 − 𝑆ˆ∥ 𝝅

a . b

Note that E[𝑝ˆ 𝑗𝑖 ] = 𝑝 𝑗𝑖 𝑞 𝑗𝑖 . We introduce the auxiliary vector 𝝅¯ as Í 𝑗 𝑝ˆ 𝑗𝑖 𝜋 𝑗 𝜋¯𝑖 = Í . 𝑗 𝑝ˆ𝑖 𝑗

First, we lower bound b . From [47, Lemma 3], we have √︄ log(𝑛) ∥𝑆 − 𝑆ˆ∥ 𝝅 ≤ ℎ∥𝑆 − 𝑆ˆ∥ 2 ≤ 80ℎ . 𝑘𝑑 max −10 1−𝑂 (𝑛

)

Next, we decompose the entry-wise error as

Furthermore, we can use a Chernoff bound to show that 𝑑 max ≥ 𝑛𝑝/2 ≥ 𝑐 0 log(𝑛)/2 with probability at least 1 − 𝑂 (𝑛 −10 ) (see proof of Theorem 3.1 below). Thus, √︄ √︂ log(𝑛) 𝛾 2 ≥ 𝛾 − 80ℎ ≥ . b ≥ 𝛾 − 80ℎ 𝑘𝑑 max 𝑐 0𝑘 2 −10 −10 1−𝑂 (𝑛

)

1−𝑂 (𝑛

x =∥ 𝝅ˆ −𝝅 ∥ ∞ ≜𝛿𝑖 𝜋ˆ𝑖 − 𝜋𝑖 = 𝜋ˆ𝑖 − 𝜋¯𝑖 + 𝜋¯𝑖 − 𝜋𝑖 Í 𝑗 (𝑝ˆ 𝑗𝑖 𝜋 𝑗 − 𝑝ˆ𝑖 𝑗 𝜋𝑖 ) a = 𝛿𝑖 + . Í 𝑗 𝑝ˆ𝑖 𝑗 b

)

10

(8)

Entrywise Error Bounds for Spectral Ranking with Semi-Random Adversaries

Then, we can decompose 𝛿𝑖 as  Í Í 1 (−𝑖 ) 𝛿𝑖 = Í ) + 𝑗 𝑝ˆ 𝑗𝑖 𝛿 𝑗(−𝑖 ) 𝑗 𝑝ˆ 𝑗𝑖 ( 𝜋ˆ 𝑗 − 𝜋ˆ 𝑗 ˆ 𝑝 𝑗 𝑖𝑗 1 2 b  Í + 𝑗 𝑝ˆ 𝑗𝑖 ( 𝜋¯ 𝑗(−𝑖 ) − 𝜋 𝑗 ) .

First, we bound a with high probability. ! √︂ 20𝑑𝑖 log(𝑛) P | a | ≤ ∥𝝅 ∥ ∞ 𝐴 𝑘  2 √︃ © © 2 ∥𝝅 ∥ ∞ 20𝑑𝑖 log(𝑛) ªª 𝑘 ­ ­ ®® ®® ≥ ­­1 − 2 exp ­­− Í ®® 2 𝑗 𝐴𝑖 𝑗 (𝜋𝑖 + 𝜋 𝑗 ) /𝑘 ®® ­ ­ « « ¬¬ ≥ 1 − 2𝑛 −10 .

3 First, we bound 1 . √︄∑︁ √︁ 1 ≤ 𝑝ˆ 2𝑗𝑖 ∥ 𝝅ˆ − 𝝅ˆ (−𝑖 ) ∥ 2 ≤ 𝑑𝑖 ∥ 𝝅ˆ − 𝝅ˆ (−𝑖 ) ∥ 2 . 𝑗 c

Next, we lower bound b .   𝑑𝑖 𝐴 P b ≥ 2(1 + ℎ) ! 𝑘 ∑︁ ≥P 𝑘 b ≥ 𝐴𝑖 𝑗 𝑝𝑖 𝑗 𝐴 2 𝑗  Í  𝑘 𝑗 𝐴𝑖 𝑗 𝑝𝑖 𝑗 ≥ 1 − exp − 8   𝑘𝑑𝑖 ≥ 1 − exp − 8(1 + ℎ)   𝑘𝑛𝑝 ≥ 1 − exp − 16(1 + ℎ)   𝑐 0𝑘 log(𝑛) ≥ 1 − 𝑛 −10 = 1 − exp − 16(1 + ℎ)

Next, we focus on 3 . 3 =

≤ b

Í

. ′ b

𝑙∉{𝑖,𝑗 } 𝑝ˆ 𝑗𝑙 + 𝑝 𝑗𝑖 𝑞 𝑗𝑖

′

Observe that a ′ and b are leave-one-out versions of a and b respectively. Thus, we can similarly conclude that √︂ 20(𝑑 𝑗 − 1) log(𝑛) ′ | a | ≤ ∥𝝅 ∥ ∞ 𝑘 −10 1−𝑂 (𝑛

)

and ′

b

≥

1−𝑂 (𝑛 −10 )

𝑑𝑗 − 1 . 2(1 + ℎ)

Thus,

∥𝝅 ∥ ∞

1−𝑂 (𝑛 −10 )

b | a ′| 3 = 𝑗 𝑝ˆ 𝑗𝑖 max ′ ≤ ′ 𝑗 b b 𝑗 √︄ 20 log(𝑛) ≤ 2 b (1 + ℎ)∥𝝅 ∥ ∞ (𝑑𝑖 − 1)𝑘 1−𝑂 (𝑛 −9 ) √︄ 80 log(𝑛) ≤ 2 b (1 + ℎ)∥𝝅 ∥ ∞ , 𝑛𝑝𝑘 −10 ∑︁ 

√︃

20𝑑𝑖 log(𝑛) 𝑘 𝑑𝑖 2(1+ℎ)

√︄ 20 log(𝑛) 𝑑𝑖 𝑘 √︄ 40 log(𝑛) . ≤ 2(1 + ℎ)∥𝝅 ∥ ∞ 𝑛𝑝𝑘 −10

= 2(1 + ℎ)∥𝝅 ∥ ∞

1−𝑂 (𝑛

a′

𝑝ˆ 𝑗𝑖

𝑗

for sufficiently large 𝑐 0 . Thus, a

𝑙∉{𝑖,𝑗 } 𝑝ˆ𝑙 𝑗 𝜋𝑙 − 𝑝ˆ 𝑗𝑙 𝜋 𝑗

Í ∑︁

1−𝑂 (𝑛



Í

)

assuming that 𝑛𝑝 ≥ 4 (which will hold for sufficiently large 𝑛). Now, we focus on 2 . To bound 2 with high probability, our strategy will be to first bound the expectation of 2 , then show that with high probability, the realization of 2 cannot deviate from the expectation too much. The expectation will be taken with respect to the connectivity of node 𝑖 only. Thus, it will be conditioned on G (−𝑖 ) , the graph G without node 𝑖. We also condition on the comparison data between 𝑖 and every other node 𝑗 ≠ 𝑖, 𝑝˜ 𝑗𝑖 . Then, we have that (𝑝ˆ𝑗𝑖 | G (−𝑖 ) , 𝒑˜ 𝑖 ) ∼ Bernoulli(𝑞 𝑗𝑖 ). Under this setting, let us first analyze E[ 2 | G (−𝑖 ) , 𝒑˜ 𝑖 ].

)

Next, we analyze 𝛿𝑖 , which was defined at (8). To do so, we introduce 𝑆ˆ (−𝑚) , a leave-one-out version of 𝑆ˆ with the 𝑚th row and column replaced by their expected values, i.e., 𝑝ˆ   𝑆ˆ𝑖 𝑗 = 𝑑𝑖 𝑗 ,    (𝑆ˆ (−𝑚) )𝑖 𝑗 ≜ 𝑝𝑖 𝑗𝑑𝑞𝑖 𝑗 ,  Í   ˆ (−𝑚) )𝑖𝑙 ,  1 − 𝑙:𝑙≠𝑖 (𝑆

a′

𝑝ˆ 𝑗𝑖

if 𝑖 ≠ 𝑚 and 𝑗 ≠ 𝑚 and 𝑖 ≠ 𝑗 if (𝑖 = 𝑚 or 𝑗 = 𝑚) and 𝑖 ≠ 𝑗, if 𝑖 = 𝑗 .

Let 𝝅ˆ (−𝑚) be the stationary distribution of 𝑆ˆ (−𝑚) . Similarly, let ¯ i.e., 𝝅¯ (−𝑚) be the leave-one-version of 𝝅, Í 𝑗∉{𝑖,𝑚} 𝑝ˆ 𝑗𝑖 𝜋 𝑗 + 𝑝𝑚𝑖 𝑞𝑚𝑖 𝜋𝑚 Í 𝜋¯𝑖(−𝑚) ≜ . 𝑗∉{𝑖,𝑚} 𝑝ˆ𝑖 𝑗 + 𝑝𝑖𝑚 𝑞𝑖𝑚

E[ 2 | G (−𝑖 ) , 𝒑˜ 𝑖 ] ∑︁ = 𝑝˜ 𝑗𝑖 𝑞 𝑗𝑖 𝛿 𝑗(−𝑖 ) 𝑗

≤

Finally, 𝑑𝑖(−𝑚) is the leave-one-out counterpart of 𝛿𝑖 ,

√︄∑︁ 𝑗

𝛿𝑖(−𝑚) ≜ 𝜋ˆ𝑖(−𝑚) − 𝜋¯𝑖(−𝑚) .

d 11

𝑞 2𝑗𝑖 ∥ 𝝅ˆ (−𝑖 ) − 𝝅¯ (−𝑖 ) ∥ 2

Lee, Makur, and Singh

 ! √︁ √ ∥𝝅 ∥ ∞ 𝑐 3 c + √︁ + 8 5(1 + ℎ) log(𝑛) 𝑝𝑘 𝛾   √ √︁ 20 + ∥𝜹 (−𝑖 ) ∥ ∞ 2 5 2𝑑𝑖 log(𝑛) + log(𝑛) 3 !  √︁ √ 2𝑠𝑑𝑖 ∥𝝅 ∥ ∞ 𝑐 3 ≤ √ c + √︁ + 8 5(1 + ℎ) log(𝑛) 𝑛 𝑝𝑘 𝛾

2𝑠𝑑𝑖 √ 𝑛 1−𝑂 (𝑛 −9 ) ≤

ª © ≤ d ­­ ∥ 𝝅ˆ (−𝑖 ) − 𝝅ˆ ∥ 2 + ∥ 𝝅ˆ − 𝝅 ∥ 2 + ∥𝝅 − 𝝅¯ (−𝑖 ) ∥ 2 ®® 𝐿𝑒𝑚𝑚𝑎 5.1 c ¬ « © ª √ ­ ® 𝑐 3 𝑛∥𝝅 ∥ ∞ √ d ­­ c + + 𝑛 ∥𝝅 − 𝝅¯ (−𝑖 ) ∥ ∞ ®® √︁ 𝛾 𝑛𝑝𝑘 ® 1−𝑂 (𝑛 −10 ) ­ | a |′ max ′ b « ¬  ! √︁ √ ∥𝝅 ∥ ∞ 𝑐 3 ≤ d c + √︁ + 8 5(1 + ℎ) log(𝑛) . 𝑝𝑘 𝛾 1−𝑂 (𝑛 −9 ) ≤

© ª ­ ® + ­­ ∥ 𝝅ˆ (−𝑖 ) − 𝝅ˆ ∥ 2 + ∥ 𝝅ˆ − 𝝅 ∥ ∞ + ∥𝝅 − 𝝅¯ (−𝑖 ) ∥ ∞ ®® ­ ® | a |′ x c max ′ b « ¬   √ √︁ 20 2 10 𝑑𝑖 log(𝑛) + log(𝑛) 3  ! √︁ √ 2𝑠𝑑𝑖 ∥𝝅 ∥ ∞ 𝑐 3 ≤ √ c + √︁ + 8 5(1 + ℎ) log(𝑛) 𝑛 𝑝𝑘 𝛾 1−𝑂 (𝑛 −9 ) √︄ ! 80 log(𝑛) + c + x + 2(1 + ℎ)∥𝝅 ∥ ∞ 𝑛𝑝𝑘   √︁ √ 20 2 10 𝑑𝑖 log(𝑛) + log(𝑛) . 3

(9)

Next, (4) implies that Í 2𝑠𝑑𝑖 𝑗 𝑞 𝑗𝑖 d ≤𝑠 √ ≤ √ . 𝑛 1−𝑂 (𝑛 −10 ) 𝑛 Next, we bound the deviation of 2 from the expectation with high probability. 2 − E[ 2 | G (−𝑖 ) , 𝒑˜ 𝑖 ] ≥

P

∥𝜹

=P

(−𝑖 )

∑︁

! √︄ 20 ª © √ ∑︁ log(𝑛) ® ∥ ∞ ­2 5 𝑞 𝑗𝑖 (1 − 𝑞 𝑗𝑖 ) log(𝑛) + 3 𝑗 ¬ « e !

Next, we bound c . From [14, Theorem 5.1], we have √ c ≤ 𝑛ℎ∥ 𝝅ˆ (−𝑖 ) − 𝝅ˆ ∥ 𝝅 ˆ 𝝅 f ∥ 𝝅ˆ (−𝑖 )T (𝑆ˆ (−𝑖 ) − 𝑆)∥ √ ≤ 𝑛ℎ 1 − |𝜆2 (𝑆)| − ∥𝑆ˆ − 𝑆 ∥ 𝝅 g

𝑝˜ 𝑗𝑖 (𝐴 𝑗𝑖 − 𝑞 𝑗𝑖 )𝛿 𝑗(−𝑖 ) ≥ e

𝑗

√ 𝑛ℎ ≤

2 1 ª 2 e ®  2 ® Í (−𝑖 ) 1 (−𝑖 ) ∥ e ˜ 𝑞 (1 − 𝑞 ) 𝑝 𝛿 ∥𝜹 + 𝑗𝑖 𝑗𝑖 𝑗𝑖 𝑗 ∞ 𝑗 3 « ¬

© ≤ 2 exp ­­−

First, we bound g . From [47, Lemma 3], we have √︄ √︂ log(𝑛) 𝛾 2 g ≤ ℎ∥𝑆ˆ − 𝑆 ∥ 2 ≤ 80ℎ ≤ ≤ 80ℎ 𝑘𝑑 max 𝑐 0𝑘 2 −10 −10

1 © ª e2 ®  2 ≤ 2 exp ­­− Í ® 1 (−𝑖 ) ∥ 2 + ∥𝜹 (−𝑖 ) ∥ e 𝑞 (1 − 𝑞 ) ∥𝜹 ∞ 𝑗𝑖 ∞ 𝑗 𝑗𝑖 3 « ¬

1−𝑂 (𝑛

Since 𝑞 𝑗𝑖 (1 − 𝑞 𝑗𝑖 ) ≤

√︄∑︁

𝑗

𝑗

𝑞 𝑗𝑖

≤

√︁

)

1−𝑂 (𝑛

)

since we assumed that 𝑐 0 ≥ 10240ℎ 2 /𝛾 2 and 𝑘 ≥ 5. To bound f , we introduce an intermediate leave-one-out matrix 𝑆ˆ (−𝑚,E ) (cf. [14, Lemma 5.6]). While 𝑆ˆ (−𝑚) is independent of both the graph edges connected to node 𝑚 and the comparison data regarding 𝑚, 𝑆ˆ (−𝑚,E ) is conditioned on the full comparison graph E, i.e., 𝑝ˆ   𝑆ˆ = 𝑖 𝑗 , if 𝑖 ≠ 𝑚 and 𝑗 ≠ 𝑚 and 𝑖 ≠ 𝑗   𝑝𝑖 𝑗 𝐴 𝑑  (−𝑚,E ) 𝑆ˆ𝑖 𝑗 ≜ 𝑖 𝑗𝑑 𝑖 𝑗 , if (𝑖 = 𝑚 or 𝑗 = 𝑚) and 𝑖 ≠ 𝑗,    1 − Í (𝑆ˆ (−𝑚,E ) ) , if 𝑖 = 𝑗 . 𝑖𝑙 𝑙:𝑙≠𝑖 

 √ √︁Í 2 ª © 1 20 ­ ® 𝑗 𝑞 𝑗𝑖 (1 − 𝑞 𝑗𝑖 ) log(𝑛) + 3 log(𝑛) ­ ® 2 2 5 ­ ® = 2 exp ­− Í ® 𝑞 (1 − 𝑞 ) 𝑗𝑖 𝑗𝑖 𝑗 ® ­   √ ­ ® √︁ Í 20 + 31 2 5 𝑗 𝑞 𝑗𝑖 (1 − 𝑞 𝑗𝑖 ) log(𝑛) + 3 log(𝑛) « ¬ ≤ 2 exp (−10 log(𝑛)) = 2𝑛 −10 . √︄∑︁

f . 𝛾− g

2𝑑𝑖 ,

1−𝑂 (𝑛 −10 )

This definition allows us to decompose f to isolate the influence of the graph edges and the comparison data.

we have 2 − E[ 2 | G (−𝑖 ) , 𝒑˜ 𝑖 ]   √ √︁ 20 ≤ ∥𝜹 (−𝑖 ) ∥ ∞ 2 5 2𝑑𝑖 log(𝑛) + log(𝑛) . 3 −10 1−𝑂 (𝑛

f √︂ (10)

≤

)

√︂

Combining (9) and (10), we have ≤ 2 ≤ E[ 2 | G (−𝑖 ) , 𝒑˜ 𝑖 ] + 2 − E[ 2 | G (−𝑖 ) , 𝒑˜ 𝑖 ] 12

ℎ (−𝑖 )T ˆ (−𝑖 ) ˆ ∥ 𝝅ˆ (𝑆 − 𝑆)∥ 2 𝑛 ª ℎ ©­ ˆ ∥2 ® ∥ 𝝅ˆ (−𝑖 )T (𝑆ˆ (−𝑖 ) − 𝑆ˆ (−𝑖,E ) )∥ 2 + ∥ 𝝅ˆ (−𝑖 )T (𝑆ˆ (−𝑖,E ) − 𝑆) ­ ® 𝑛 i h « ¬

Entrywise Error Bounds for Spectral Ranking with Semi-Random Adversaries

Thus, for 𝑗 ≠ 𝑖, we have

First, we bound h . Observe that ˆ (−𝑖 )

ˆ (−𝑖,E )

(𝑆 −𝑆 ) 𝑗𝑙 𝑝 𝑗𝑙 (𝑞 𝑗𝑙 −𝐴 𝑗𝑙 )   ,  𝑑    𝑝 𝑗𝑖 (−𝑞 𝑗𝑖 +𝐴 𝑗𝑖 )   , = Í 𝑑𝑝𝑖𝑚 (−𝑞𝑖𝑚 +𝐴𝑖𝑚 )  𝑚≠𝑖 ,  𝑑     0, 

ˆ 𝑗 ( 𝝅ˆ (−𝑖 )T (𝑆ˆ (−𝑖,E ) − 𝑆)) if (𝑗 = 𝑖 or 𝑙 = 𝑖) and 𝑗 ≠ 𝑙,

= 𝜋ˆ 𝑗(−𝑖 )

if 𝑗 = 𝑙 and 𝑗 ≠ 𝑖, if 𝑗 = 𝑙 = 𝑖, otherwise.

2𝐴𝑖 𝑗 ∥ 𝝅ˆ (−𝑖 ) ∥ ∞ |𝑝𝑖 𝑗 − 𝑝ˆ𝑖 𝑗 | 𝑑 √︂ 2𝐴𝑖 𝑗 ∥ 𝝅ˆ (−𝑖 ) ∥ ∞ 5 log(𝑛) ≤ . 𝑑 𝑘 −10

≤

Note that (𝝅 T (𝑆ˆ (−𝑖 ) − 𝑆ˆ (−𝑖,E ) )) 𝑗 ( 𝑝 (−𝑞 +𝐴 ) 𝑝 (𝑞 −𝐴 ) 𝜋 𝑗 𝑗𝑖 𝑑𝑗𝑖 𝑗𝑖 + 𝜋𝑖 𝑖 𝑗 𝑖𝑑𝑗 𝑖 𝑗 = 0, = Í Í 𝑝 (−𝑞 +𝐴 ) 𝑝𝑙𝑖 (𝑞𝑙𝑖 −𝐴𝑙𝑖 ) + 𝜋𝑖 𝑙≠𝑖 𝑖𝑙 𝑑𝑖𝑙 𝑖𝑙 = 0, 𝑙≠𝑖 𝜋𝑙 𝑑

1−𝑂 (𝑛

if 𝑗 ≠ 𝑖, if 𝑗 = 𝑖,

ˆ 𝑖 ( 𝝅ˆ (−𝑖 )T (𝑆ˆ (−𝑖,E ) − 𝑆)) =

1−𝑂 (𝑛

v u t

!2 !2 √︂ √︂ 2∥ 𝝅ˆ (−𝑖 ) ∥ ∞ 5𝑑𝑖 log(𝑛) 2∥ 𝝅ˆ (−𝑖 ) ∥ ∞ 5 log(𝑛) ≤ 𝑑𝑖 + 𝑑 𝑘 𝑑 𝑘 1−𝑂 (𝑛 −9 ) √︂ 2∥ 𝝅ˆ (−𝑖 ) ∥ ∞ 10𝑑𝑖 log(𝑛) = . 𝑑 𝑘 Putting it all together, we have

𝑙≠𝑖

( 𝜋ˆ𝑙(−𝑖 ) − 𝜋𝑙 )𝑝𝑙𝑖 − ( 𝜋ˆ𝑖(−𝑖 ) − 𝜋𝑖 )𝑝𝑖𝑙 ∑︁

(𝑞𝑙𝑖 − 𝐴𝑙𝑖 )

𝑑 𝑙≠𝑖

≤

)

i

∑︁ 𝑝 (−𝑞 + 𝐴 ) 𝑝𝑙𝑖 (𝑞𝑙𝑖 − 𝐴𝑙𝑖 ) 𝑖𝑙 𝑖𝑙 𝑖𝑙 + ( 𝜋ˆ𝑖(−𝑖 ) − 𝜋𝑖 ) 𝑑 𝑑

𝑙≠𝑖

∑︁ 𝐴𝑖 𝑗 (−𝑝𝑖 𝑗 + 𝑝ˆ𝑖 𝑗 ) 𝐴 𝑗𝑖 (𝑝 𝑗𝑖 − 𝑝ˆ 𝑗𝑖 ) + 𝜋ˆ𝑖(−𝑖 ) 𝑑 𝑑 𝑗≠𝑖

Thus,

𝑙≠𝑖

≤ max

𝜋ˆ 𝑗(−𝑖 )

𝑗≠𝑖

(( 𝝅ˆ (−𝑖 ) − 𝝅) T (𝑆ˆ (−𝑖 ) − 𝑆ˆ (−𝑖,E ) ))𝑖 (𝜋ˆ𝑙(−𝑖 ) − 𝜋𝑙 )

∑︁

2∥ 𝝅ˆ (−𝑖 ) ∥ ∞ ∑︁ ≤ 𝐴𝑖 𝑗 (𝑝𝑖 𝑗 − 𝑝ˆ𝑖 𝑗 ) 𝑑 𝑗≠𝑖 √︂ 2∥ 𝝅ˆ (−𝑖 ) ∥ ∞ 5𝑑𝑖 log(𝑛) ≤ . 𝑑 𝑘 −10

Finally, for 𝑗 = 𝑖,

∑︁

)

When 𝑗 = 𝑖,

thus 𝝅ˆ (−𝑖 )T (𝑆ˆ (−𝑖 ) − 𝑆ˆ (−𝑖,E ) ) = ( 𝝅ˆ (−𝑖 ) − 𝝅) T (𝑆ˆ (−𝑖 ) − 𝑆ˆ (−𝑖,E ) ). Furthermore, for all 𝑗 ≠ 𝑙, since |(𝑆ˆ (−𝑖 ) − 𝑆ˆ (−𝑖,E ) ) 𝑗𝑙 | ≤ 𝑑1 when 𝐴 𝑗𝑙 = 1 𝑞 and |(𝑆ˆ (−𝑖 ) − 𝑆ˆ (−𝑖,E ) ) 𝑗𝑙 | ≤ 𝑑𝑗𝑙 when 𝐴 𝑗𝑙 = 0, we have for all 𝑗 ≠ 𝑖, ( 2 ˆ (−𝑖 ) ∥𝝅 − 𝝅 ∥ ∞, if 𝐴 𝑗𝑖 = 1, (−𝑖 ) T ˆ (−𝑖 ) (−𝑖,E ) ˆ ˆ (( 𝝅 − 𝝅) (𝑆 −𝑆 )) 𝑗 ≤ 𝑑2𝑝 (−𝑖 ) ˆ ∥ 𝝅 − 𝝅 ∥ ∞, otherwise. 𝑑

=

𝐴𝑖 𝑗 (𝑝𝑖 𝑗 − 𝑝ˆ𝑖 𝑗 ) 𝐴 𝑗𝑖 (−𝑝 𝑗𝑖 + 𝑝ˆ 𝑗𝑖 ) + 𝜋ˆ𝑖(−𝑖 ) 𝑑 𝑑

2∥ 𝝅ˆ (−𝑖 ) − 𝝅 ∥ ∞ ∑︁ (𝑞𝑙𝑖 − 𝐴𝑙𝑖 ) 𝑑 𝑙≠𝑖

c √ ≤ 𝑛ℎ

√︄ 2∥ 𝝅ˆ (−𝑖 ) − 𝝅 ∥ ∞ © √ ∑︁ 20 ª ≤ 𝑞 𝑗𝑖 (1 − 𝑞 𝑗𝑖 ) log(𝑛) + log(𝑛) ® ­2 5 𝑑 3 −10 𝑗 1−𝑂 (𝑛 ) ¬ «   20 2∥ 𝝅ˆ (−𝑖 ) − 𝝅 ∥ ∞ √ √︁ ≤ 2 10 𝑑𝑖 log(𝑛) + log(𝑛) . 𝑑 3 −10 1−𝑂 (𝑛

)

1−𝑂 (𝑛

Thus, we have h v u  2  2 u u u t 𝑑𝑖 𝑑2 ∥ 𝝅ˆ (−𝑖 ) − 𝝅 ∥ ∞ + (𝑛 − 𝑑𝑖 − 1) 2𝑝 ˆ (−𝑖 ) − 𝝅 ∥ ∞ 𝑑 ∥𝝅   √ √︁  2 ≤ (−𝑖 ) log(𝑛) + 2∥ 𝝅ˆ 𝑑 −𝝅 ∥ ∞ 2 10 𝑑𝑖 log(𝑛) + 20 1−𝑂 (𝑛 −10 ) 3  √︁  √ √︁ √ 40 ∥ 𝝅ˆ (−𝑖 ) − 𝝅 ∥ ∞ ≤ 2 𝑑𝑖 + 2𝑝 𝑛 + 4 10 𝑑𝑖 log(𝑛) + log(𝑛) . 3 𝑑 Next, we bound i . Observe that ˆ 𝑗𝑙 (𝑆ˆ (−𝑖,E ) − 𝑆)   𝐴 𝑗𝑙 (𝑝 𝑗𝑙 −𝑝ˆ 𝑗𝑙 ) ,    𝐴 𝑗𝑖 (−𝑝𝑑 𝑗𝑖 +𝑝ˆ 𝑗𝑖 )    , = Í 𝑑𝐴 (−𝑝 +𝑝ˆ ) 𝑖𝑚 𝑖𝑚 𝑖𝑚  ,  𝑚≠𝑖  𝑑    0, 

f 𝛾− g √ 2 𝑛ℎ ≤ f −9 𝛾

if (𝑗 = 𝑖 or 𝑙 = 𝑖) and 𝑗 ≠ 𝑙, if 𝑗 = 𝑙 and 𝑗 ≠ 𝑖, if 𝑗 = 𝑙 = 𝑖, otherwise.

)

2ℎ h + i ≤ 𝛾 √︂  2ℎ 2∥ 𝝅ˆ (−𝑖 ) ∥ ∞ 10𝑑𝑖 log(𝑛) ≤ 𝛾 𝑑 𝑘  √︁   √︁ √ ∥ 𝝅ˆ (−𝑖 ) − 𝝅 ∥ ∞ 40 + 2 𝑑𝑖 + 2𝑝 𝑛 + 4 10𝑑𝑖 log(𝑛) + log(𝑛) 3 𝑑 √︂  20 log(𝑛) 4ℎ ≤ ∥ 𝝅ˆ (−𝑖 ) ∥ ∞ 𝛾 𝑑𝑘 1−𝑂 (𝑛 −10 ) √    1 2 4 5 40 + √ +√ + √ + ∥ 𝝅ˆ (−𝑖 ) − 𝝅 ∥ ∞ 𝑐 0 3𝑐 0 𝑛 𝑑 √︂ 20 log(𝑛) 4ℎ ≤ ∥𝝅 ∥ ∞ 𝛾 𝑑𝑘 ! √︂ √  20 1 2 4 5 40 (−𝑖 ) ˆ + +√ +√ + √ + ∥𝝅 − 𝝅 ∥∞ 𝑐 0𝑘 𝑐 0 3𝑐 0 𝑛 𝑑 13

Lee, Makur, and Singh

√ √︂ 8 5ℎ log(𝑛) ∥𝝅 ∥ ∞ 𝛾 𝑑𝑘

≤

√︄ ≤ 2(1 + ℎ)∥𝝅 ∥ ∞ 1−𝑂 (𝑛 −9 )

! 𝛾 1 8ℎ 1 1 + √ + √︁ + √ + √ + ∥ 𝝅ˆ (−𝑖 ) − 𝝅 ∥ ∞ 4 10 8 5 log(𝑛) 𝛾 𝑛 2 2 192ℎ √ √︂ 8 5ℎ log(𝑛) 1 ≤ ∥𝝅 ∥ ∞ + ∥ 𝝅ˆ (−𝑖 ) − 𝝅 ∥ ∞ 𝛾 𝑑𝑘 2 √︂ √ ª 1© 8 5ℎ log(𝑛) ∥𝝅 ∥ ∞ + ­­ ∥ 𝝅ˆ (−𝑖 ) − 𝝅ˆ ∥ 2 + ∥ 𝝅ˆ − 𝝅 ∥ ∞ ®® . ≤ 𝛾 𝑑𝑘 2 c « ¬

! √  4 5 40 ª® + c + x + 2(1 + ℎ)∥𝝅 ∥ ∞ √ + 𝑐 0 3𝑐 0 ® ¬ √︄   √ √ log(𝑛) 16𝛾 ≤ 8 5 + 32 5(1 + ℎ)𝑠 + √ (1 + ℎ)∥𝝅 ∥ ∞ 𝑛𝑝𝑘 5 √︄

80 log(𝑛) 𝑛𝑝𝑘

√ √︂ 16 5ℎ log(𝑛) c ≤ ∥𝝅 ∥ ∞ + ∥ 𝝅ˆ − 𝝅 ∥ ∞ . 𝑑𝑘 −9 𝛾

4(1 + ℎ)𝑠𝑐 3 ∥𝝅 ∥ ∞ 2𝛾 x + √︁ 5 𝛾 𝑛𝑝𝑘    2(1 + ℎ) 4𝑠 (1 + ℎ) 2𝛾 + max + c + √ √ 𝑖 5 𝑛 𝑑𝑖 √︄   √ √ log(𝑛) 16𝛾 ≤ 8 5 + 32 5(1 + ℎ)𝑠 + √ (1 + ℎ)∥𝝅 ∥ ∞ 𝑛𝑝𝑘 5 1−𝑂 (𝑛 −8 ) +

)

Finally, combining all the intermediate results, we have x = ∥ 𝝅ˆ − 𝝅 ∥ ∞ a = max 𝛿𝑖 + 𝑖

b

4(1 + ℎ)𝑠𝑐 3 ∥𝝅 ∥ ∞ 2𝛾 x + √︁ 5 𝛾 𝑛𝑝𝑘 ! √ 2 2(1 + ℎ) 4𝑠 (1 + ℎ) 2𝛾 + √︁ + + √ 5 𝑛 𝑐 0 log(𝑛) √︄ ! √ 16 10ℎ log(𝑛) ∥𝝅 ∥ ∞ + x 𝛾 𝑛𝑝𝑘

√︄ ≤ max |𝛿𝑖 | + 2(1 + ℎ)∥𝝅 ∥ ∞ 1−𝑂 (𝑛 −9 )

𝑖

= max 𝑖

≤ max 1−𝑂 (𝑛 −8 )

𝑖

+

40 log(𝑛) 𝑛𝑝𝑘 √︄

1 + 2 + 3 + 2(1 + ℎ)∥𝝅 ∥ ∞ b

40 log(𝑛) 𝑛𝑝𝑘

1 ©­√︁ 𝑑𝑖 c b ­ «

√︁ √ ∥𝝅 ∥ ∞ 𝑐 3 c + √︁ + 8 5(1 + ℎ) log(𝑛) 𝛾 𝑝𝑘 √︄ ! 80 log(𝑛) + c + x + 2(1 + ℎ)∥𝝅 ∥ ∞ 𝑛𝑝𝑘   √ √︁ 20 2 10 𝑑𝑖 log(𝑛) + log(𝑛) 3 √︄ 80 log(𝑛) ª® + 2 b (1 + ℎ) ∥𝝅 ∥ ∞ 𝑛𝑝𝑘 ® ¬ √︄ 80 log(𝑛) ≤ 2(1 + ℎ) ∥𝝅 ∥ ∞ 𝑛𝑝𝑘 −9 2𝑠𝑑𝑖 + √ 𝑛

1−𝑂 (𝑛



A √ √ 16(1+ℎ)𝛾 8 5(1 + ℎ) + 32 5(1 + ℎ) 2𝑠 + √

!

5 © ª = ­ 4(1+ℎ)𝑠𝑐 3 64√5ℎ (1+ℎ) 64√10ℎ (1+ℎ)𝑠 64ℎ ® √ √ + 𝛾 log(𝑛) + √ + + 𝑛 10 ¬ 𝛾 𝑐 0 log(𝑛) « ! √ 4𝛾 2 2(1 + ℎ) 4𝑠 (1 + ℎ) + + + √︁ x. √ 5 𝑛 𝑐 0 log(𝑛)

+

 ! √︁ √ ∥𝝅 ∥ ∞ 𝑐 3 c + √︁ + 8 5(1 + ℎ) log(𝑛) 𝑝𝑘 𝛾

c + x + 2(1 + ℎ)∥𝝅 ∥ ∞

√︄ 80 log(𝑛) 𝑛𝑝𝑘

√︄ log(𝑛) ∥𝝅 ∥ ∞ 𝑛𝑝𝑘

B

)

© c 2𝑠 + 2(1 + ℎ) max ­­ √ + √ 𝑖 𝑛 𝑑𝑖 «

 ! √︁ √ ∥𝝅 ∥ ∞ 𝑐 3 + 8 5(1 + ℎ) log(𝑛) c + √︁ 𝑝𝑘 𝛾

© c 2𝑠 + 2(1 + ℎ) max ­­ √ + √ 𝑖 𝑛 𝑑𝑖 «

Thus,

1−𝑂 (𝑛

80 log(𝑛) 𝑛𝑝𝑘

Observe that for sufficiently large 𝑛, √  √ √ 1 A ≤ (1 + ℎ)(4𝑠𝑐 3 + 64 5ℎ) + 32 5(1 + ℎ) + 128 10(1 + ℎ) 2𝑠 , 𝛾 D C 9 B ≤ . 10 Thus,   √︄ log(𝑛) ∥ 𝝅ˆ − 𝝅 ∥ ∞ 𝑐1 ≤ + 𝑐2 ∥𝝅 ∥ ∞ 𝛾 𝑛𝑝𝑘 −8 1−𝑂 (𝑛

)

where the constants 𝑐 1 = 10 C and 𝑐 2 = 10 D only depend on ℎ, 𝑠, and 𝑐 3 but not 𝑛 or 𝑝. □

!

C

√ √︁ ª 2 10 𝑑𝑖 log(𝑛) + 20 3 log(𝑛) ® ® 𝑑𝑖 ¬

Proof of Theorem 4.1 Proof. First, recall that Í

𝑗:𝑗≠𝑖 𝑝ˆ 𝑗𝑖 𝑤 𝑗𝑖 𝜋ˆ 𝑗

𝜋ˆ𝑖 = Í 14

. 𝑗:𝑗≠𝑖 𝑝ˆ𝑖 𝑗 𝑤 𝑖 𝑗

Entrywise Error Bounds for Spectral Ranking with Semi-Random Adversaries

As in the proof of Theorem 3.1, we define the auxiliary vector 𝝅¯ as Í 𝑗:𝑗≠𝑖 𝑝ˆ 𝑗𝑖 𝑤 𝑗𝑖 𝜋 𝑗 𝜋¯𝑖 ≜ Í . 𝑗:𝑗≠𝑖 𝑝ˆ𝑖 𝑗 𝑤 𝑖 𝑗

due to Hoeffding’s inequality. Thus, with high probability, we have √︂ 10𝑛 log(𝑛)𝑝 𝝅 b ≥ 𝑑 min − ∥𝝅 ∥ ∞ 𝑘 1−𝑂 (𝑛 −10 ) √︄ (a) 𝝅 10𝑛 log(𝑛)𝑝𝜆𝑛−1 (𝐿𝑊 ) 2 ≥ 𝑑 min − ∥𝝅 ∥ ∞ 640ℎ 2𝑛 log(𝑛)𝑝

Next, we decompose the entry-wise error as 𝜋ˆ𝑖 − 𝜋𝑖 𝜋¯𝑖 − 𝜋𝑖 𝜋ˆ𝑖 − 𝜋¯𝑖 = + 𝜋𝑖 𝜋𝑖 𝜋𝑖 Í 𝑗:𝑗≠𝑖 𝑤 𝑖 𝑗 (𝑝ˆ 𝑗𝑖 𝜋 𝑗 − 𝑝ˆ𝑖 𝑗 𝜋𝑖 ) a 𝜋ˆ − 𝜋¯ (a) 𝑖 𝑖 + = Í 𝜋 𝑖 𝜋𝑖 𝑗:𝑗≠𝑖 𝑤𝑖 𝑗 𝑝ˆ𝑖 𝑗 b

(b) 𝜆𝑛−1 (𝐿𝑊 𝝅 )

≥

2

c ≥

4 where (a) follows from the 𝑘 assumption, (b) is due to 𝜆𝑛−1 (𝐿𝑊 𝝅 ) ≤ 𝝅 from [55, Lemma 18], and (c) follows from (11). 2𝑑 min Next, we focus on c , which we will denote with 𝛿𝑖 . Note that Í 𝜋ˆ𝑖 − 𝜋¯𝑖 𝑗 𝑤 𝑗𝑖 𝑝ˆ 𝑗𝑖 ( 𝜋ˆ 𝑗 − 𝜋 𝑗 ) Í c = 𝛿𝑖 = = 𝜋𝑖 𝜋𝑖 𝑗 𝑤𝑖 𝑗 𝑝ˆ𝑖 𝑗 Í Í 𝑗 𝑤 𝑗𝑖 𝑝ˆ 𝑗𝑖 𝜋 𝑗 𝛿 𝑗 𝑗 𝑤 𝑗𝑖 𝑝ˆ 𝑗𝑖 ( 𝜋¯ 𝑗 − 𝜋 𝑗 ) Í Í = + , 𝜋𝑖 𝑗 𝑤𝑖 𝑗 𝑝ˆ𝑖 𝑗 𝜋𝑖 𝑗 𝑤𝑖 𝑗 𝑝ˆ𝑖 𝑗 thus (𝜋𝑖

2 , 𝑛 10 Í where (a) is due to Hoeffding’s inequality and (b) is due to 𝑗:𝑗≠𝑖 𝑤𝑖2𝑗 ≤ Í 𝑗:𝑗≠𝑖 𝑤 𝑖 𝑗 ≤ 2𝑛𝑝. Next, to lower bound b , we first define the 𝝅-weighted Lapla𝝅 cian matrix 𝐿𝑊 𝝅 and the corresponding quantity 𝑑 min , ∑︁ 𝜋𝑖 𝜋 𝑗 𝐿𝑊 𝑤𝑖 𝑗 (𝒆𝑖 − 𝒆 𝑗 )(𝒆𝑖 − 𝒆 𝑗 ) T, 𝝅 ≜ 𝜋 + 𝜋𝑗 𝑖< 𝑗 ≤𝑛 𝑖

𝑗:𝑗≠𝑖

𝑤 𝑗𝑖 𝑝ˆ 𝑗𝑖 ( 𝜋¯ 𝑗 − 𝜋 𝑗 ).

𝑗

(12)

(

−𝑤 𝑗𝑖 𝑝ˆ 𝑗𝑖 𝜋 𝑗 , if 𝑖 ≠ 𝑗, Í 𝜋𝑖 𝑘 𝑤𝑖𝑘 𝑝ˆ𝑖𝑘 , otherwise, ∑︁ 𝑟𝑖 ≜ 𝑤 𝑗𝑖 𝑝ˆ 𝑗𝑖 ( 𝜋¯ 𝑗 − 𝜋 𝑗 ).

(𝐿ˆ𝑊 𝝅 )𝑖 𝑗 ≜

𝑗 𝑊 ˆ𝑊 Note that E[𝐿ˆ𝑊 𝝅 ] = 𝐿𝝅 and 𝐿𝝅 is column-stochastic (but not necessarily row-stochastic, unlike 𝐿𝑊 𝝅 ). Next, we use Bernstein’s inequal𝑊 ity for matrices [54] to bound ∥ 𝐿ˆ𝑊 𝝅 − 𝐿𝝅 ∥ 2 with high probability. Let 𝑟𝑖 𝑗𝑙 be the 𝑙 ∈ [𝑘]-th comparison result for the pair (𝑖, 𝑗) with Í 𝑟𝑖 𝑗𝑙 ∼ Bernoulli(𝑝𝑖 𝑗 ), 𝑟 𝑗𝑖𝑙 = 1 − 𝑟𝑖 𝑗𝑙 , and 𝑙 ∈ [𝑘 ] 𝑟𝑖 𝑗𝑙 /𝑘 = 𝑝ˆ𝑖 𝑗 . For all (𝑖, 𝑗) ∈ E with 𝑖 > 𝑗 and 𝑙 ∈ [𝑘], define the matrix 𝑋 𝑗𝑖𝑙 to be

𝜋𝑖 𝜋 𝑗 ∥𝝅 ∥ ∞ ∥𝝅 ∥ ∞ ≤ , ≤ 2ℎ 𝜋𝑖 + 𝜋 𝑗 2

1 𝑤 𝑗𝑖 (𝑟 𝑗𝑖𝑙 − 𝑝 𝑗𝑖 )(𝒆 𝑗 − 𝒆𝑖 )(𝜋 𝑗 𝒆 𝑗 − 𝜋𝑖 𝒆𝑖 ) T . 𝑘 Observe that E[𝑋 𝑗𝑖𝑙 ] = 0𝑛×𝑛 , 𝑋 𝑗𝑖𝑙 ≜

(11)

T T ∥E[𝑋 𝑗𝑖𝑙 𝑋 𝑗𝑖𝑙 ] ∥ 2 = ∥E[𝑋 𝑗𝑖𝑙 𝑋 𝑗𝑖𝑙 ] ∥2 =

≤ d

and ! 10𝑛 log(𝑛)𝑝 𝑘 2 √︃

 © 2 ∥𝝅 ∥ ∞ 10𝑛 log(𝑛)𝑝 𝑘 ­ ≥ 1 − exp ­­− Í𝑛 2 2 𝜋𝑖 𝑗=1 𝑤𝑖 𝑗 /𝑘 ­ «

∑︁

where

Note that since

√︂

𝑤 𝑗𝑖 𝑝ˆ 𝑗𝑖 𝜋 𝑗 𝛿 𝑗 =

𝐿ˆ𝑊 𝝅 𝜹 = 𝒓,

𝑛 ∑︁ 𝜋𝑖 𝜋 𝑗 𝑤𝑖 𝑗 . 𝜋 + 𝜋𝑗 𝑗=1 𝑖

𝝅 ≥𝑑 min

∑︁

𝑤𝑖 𝑗 𝑝ˆ𝑖 𝑗 )𝛿𝑖 −

This can be re-expressed as

≥ 1 − 2 exp (−10 log(𝑛)) = 1 −

P d ≥ −∥𝝅 ∥ ∞

∑︁ 𝑗

(b)

we have that (cf. [55, Section 4.1]) ∥𝝅 ∥ ∞ ∥𝝅 ∥ ∞ 𝜆𝑛−1 (𝐿𝑊 ) ≤ 𝜆𝑛−1 (𝐿𝑊 𝜆𝑛−1 (𝐿𝑊 ). 𝝅 ) ≤ 2ℎ 2 Then, 𝑛 𝑛 ∑︁ ∑︁ 𝜋𝑖 𝜋 𝑗 b = 𝑤 𝑖 𝑗 + 𝜋𝑖 𝑤𝑖 𝑗 (𝑝ˆ𝑖 𝑗 − 𝑝𝑖 𝑗 ), 𝜋 + 𝜋𝑗 𝑗=1 𝑗=1 𝑖

∥𝝅 ∥ ∞ 𝜆𝑛−1 (𝐿𝑊 ) 8ℎ

(c) 𝜆𝑛−1 (𝐿𝑊 𝝅 )

where (a) follows from 𝑤𝑖 𝑗 = 𝑤 𝑗𝑖 . First, we upper bound the magnitude of a with high probability. ! √︂ 40𝑛 log(𝑛)𝑝 P | a | ≤ ∥𝝅 ∥ ∞ 𝑘  2 √︃ © 2 ∥𝝅 ∥ ∞ 40𝑛 log(𝑛)𝑝 ª 𝑘 ­ ® (a) ­ ® ≥ 1 − 2 exp ­− Í 2 (𝜋 + 𝜋 ) 2 /𝑘 ® 𝑤 𝑗 ­ ® 𝑗:𝑗≠𝑖 𝑖 𝑗 𝑖 « ¬ ! 20𝑛 log(𝑛)𝑝 ≥ 1 − 2 exp − Í 2 𝑗:𝑗≠𝑖 𝑤 𝑖 𝑗

𝝅 𝑑 min ≜ min 𝑖 ∈ [𝑛]

−

and

2 2 𝑤 𝑝 𝑗𝑖 (1 − 𝑝 𝑗𝑖 ) (𝜋𝑖2 + 𝜋 𝑗2 ) 𝑘 2 𝑗𝑖

𝑤 2𝑗𝑖 ∥𝝅 ∥ 2∞ , 𝑘2

√︃ 1 2∥𝝅 ∥ ∞ ∥𝑋 𝑗𝑖𝑙 ∥ 2 = 𝑤 𝑗𝑖 |𝑟 𝑗𝑖𝑙 − 𝑝 𝑗𝑖 | 2(𝜋𝑖2 + 𝜋 𝑗2 ) ≤ , 𝑘 𝑘 ∑︁ ∑︁ 𝑊 𝑋 𝑗𝑖𝑙 = 𝐿ˆ𝑊 𝝅 − 𝐿𝝅 . (𝑖,𝑗 ) ∈ E,𝑖> 𝑗 𝑙 ∈ [𝑘 ]

ª ® ®≥1− 1 ® 𝑛 10 ® ¬

Thus, √︂ 𝑊 P ∥ 𝐿ˆ𝑊 𝝅 − 𝐿𝝅 ∥ 2 ≥ ∥𝝅 ∥ ∞

15

40𝑛 2 𝑝 log(𝑛) 𝑘

!

Lee, Makur, and Singh

! 𝜋 𝑗 − 𝜋¯ 𝑗 𝜋𝑗 𝜆𝑛−1 (𝐿𝑊 𝝅 ) 1−𝑂 (𝑛 −10 ) √︃ 40𝑛 log(𝑛)𝑝 4∥𝝅 ∥ ∞ ª 4𝑤𝑖 𝑗 ∥𝝅 ∥ 2∞ (𝑝𝑖 𝑗 − 𝑝ˆ𝑖 𝑗 ) ©­ 𝑘 ® 1 + ≤ ­ ® 𝑊 𝑊 𝜆 (𝐿 𝜆 (𝐿 ) ) 𝑛−1 𝑛−1 −10 𝝅 𝝅 1−𝑂 (𝑛 ) « ¬ 16ℎ𝑤𝑖 𝑗 ∥𝝅 ∥ ∞ (𝑝𝑖 𝑗 − 𝑝ˆ𝑖 𝑗 ) ≤ , 𝜆𝑛−1 (𝐿𝑊 )

2

40𝑛 𝑝 log(𝑛) © ª −∥𝝅 ∥ 2∞ 2𝑘 ® ≤ 2𝑛 exp ­­ √︃ 2 2 𝑝 log(𝑛) ® 2∥𝝅 ∥ 𝑛 𝑊 𝑊 ∞ ˆ 𝑘 « var(𝐿𝝅 − 𝐿𝝅 ) + 3𝑘 ¬

−20𝑛 2 𝑝 log(𝑛) ª® √︃ ® 2 2 𝑝 + 2 𝑛 𝑝 log(𝑛) 𝑛 3 𝑘 « ¬

© ≤ 2𝑛 exp ­­

≤ 2𝑛 exp(−10 log(𝑛)) ≤ 2𝑛 −9 .

1+

′

Thus, from the assumption on 𝑘, we have √︂ ℎ 40𝑛 2 𝑝 log(𝑛) 𝜆𝑛−1 (𝐿𝑊 𝝅 ) 𝑊 ∥ 𝐿ˆ𝑊 − 𝐿 ∥ ≤ ≤ . 𝝅 𝝅 2 𝑛 𝑘 2 −9 1−𝑂 (𝑛

4𝑤𝑖 𝑗 ∥𝝅 ∥ 2∞ (𝑝𝑖 𝑗 − 𝑝ˆ𝑖 𝑗 )

≤

where b is a leave-one-out version of b and can be bounded similarly. Thus, ∑︁ 16ℎ𝑤𝑖 𝑗 ∥𝝅 ∥ ∞ (𝑝𝑖 𝑗 − 𝑝ˆ𝑖 𝑗 ) d ≤ 𝜆𝑛−1 (𝐿𝑊 ) 1−𝑂 (𝑛 −9 ) 𝑗 √︃ 10𝑛 log(𝑛)𝑝 16ℎ∥𝝅 ∥ ∞ 𝑘 ≤ . 𝜆𝑛−1 (𝐿𝑊 ) −10

)

Therefore, by taking the ℓ 2 norm on both sides of (12), we get 𝑊 𝑊 ˆ𝑊 ∥𝒓 ∥ 2 = ∥ 𝐿ˆ𝑊 𝝅 𝜹 ∥ 2 ≥ ∥𝐿𝝅 𝜹 ∥ 2 − ∥ 𝐿𝝅 − 𝐿𝝅 ∥ 2 ∥𝜹 ∥ 2   𝜆𝑛−1 (𝐿𝑊 |𝜹 T 1𝑛 | 𝝅 ) − ∥𝜹 ∥ 2 ≥ 𝜆𝑛−1 (𝐿𝑊 𝝅 ) ∥𝜹 ∥ 2 − √ 2 𝑛 −9 1−𝑂 (𝑛 )   ∥𝜹 ∥ 2 |𝜹 T 1𝑛 | − √ = 𝜆𝑛−1 (𝐿𝑊 , 𝝅 ) 2 𝑛

1−𝑂 (𝑛

)

Next, e =

∑︁

Í

𝑙∉{𝑖,𝑗 } 𝑤𝑙 𝑗 (𝑝ˆ𝑙 𝑗 𝜋𝑙 − 𝑝ˆ 𝑗𝑙 𝜋 𝑗 )

𝑤 𝑗𝑖 𝑝ˆ 𝑗𝑖 Í

𝑙∉{𝑖,𝑗 } 𝑤 𝑗𝑙 𝑝ˆ 𝑗𝑙 + 𝑤 𝑗𝑖 𝑝 𝑗𝑖

𝑗

thus f



 ∥𝒓 ∥ 2 |𝜹 T 1𝑛 | + . √ 𝑛 𝜆 (𝐿𝑊 ) 1−𝑂 (𝑛 −9 ) 𝑛−1 𝝅

∥𝜹 ∥ 2 ≤ 2

≤

Í Í 𝑗

1−𝑂 (𝑛 −9 )

Next, we bound each element of 𝒓. ∑︁ 𝑟𝑖 = 𝑤 𝑗𝑖 𝑝ˆ 𝑗𝑖 ( 𝜋¯ 𝑗 − 𝜋 𝑗 )

𝑙∉{𝑖,𝑗 } 𝑤 𝑗𝑖 𝑤𝑙 𝑗 (𝑝ˆ𝑙 𝑗 𝜋𝑙 − 𝑝ˆ 𝑗𝑙 𝜋 𝑗 ) . 𝜆𝑛−1 (𝐿𝑊 𝝅 )

Using Hoeffding’s inequality, ! 80 log(𝑛) P | f | ≤ ∥𝝅 ∥ ∞𝑛𝑝 𝑘  2 √︃ 80 log(𝑛) © ª 2 ∥𝝅 ∥ ∞𝑛𝑝 𝑘 ­ ® ® ≥ 1 − 2 exp ­­− Í Í ® 2 2 2 ­ 𝑗 𝑙∉{𝑖,𝑗 } 𝑤 𝑗𝑖 𝑤𝑙 𝑗 (𝜋𝑙 + 𝜋 𝑗 ) /𝑘 ® « ¬ ! 40𝑛 2 𝑝 2 log(𝑛) ≥ 1 − 2 exp − Í Í 2 2 𝑗 𝑙∉{𝑖,𝑗 } 𝑤 𝑗𝑖 𝑤𝑙 𝑗 √︂

𝑗

=

4∥𝝅 ∥ ∞

∑︁

𝑤 𝑗𝑖 𝑝ˆ 𝑗𝑖 ( 𝜋¯ 𝑗 − 𝜋¯ 𝑗(−𝑖 ) ) +

∑︁

𝑤 𝑗𝑖 𝑝ˆ 𝑗𝑖 (𝜋¯ 𝑗(−𝑖 ) − 𝜋 𝑗 ),

𝑗

𝑗

e

d

where 𝜋¯ 𝑗(−𝑖 ) is the leave-one-out version of 𝜋¯ 𝑗 , Í 𝑙∉{𝑖,𝑗 } 𝑤𝑙 𝑗 𝑝ˆ𝑙 𝑗 𝜋𝑙 + 𝑤 𝑖 𝑗 𝑝𝑖 𝑗 𝜋𝑖 (−𝑖 ) 𝜋¯ 𝑗 . ≜ Í 𝑙∉{𝑖,𝑗 } 𝑤 𝑗𝑙 𝑝ˆ 𝑗𝑙 + 𝑤 𝑗𝑖 𝑝 𝑗𝑖 First, note the identity ′

′

′

′

( 1 + 2 )( 4 − 4 ) 1 + 2 1 + 2 2 − 2 − + ′ = ′ . 3 + 4 3 + 4 3 + 4 ( 3 + 4 )( 3 + 4 )

≥ 1 − 2 exp (−10 log(𝑛)) = 1 −

2 , 𝑛 10

Thus, Thus, 𝜋¯ 𝑗(−𝑖 ) − 𝜋¯ 𝑗

e ≤

1 ∑︁ =

𝑙∉{𝑖,𝑗 }

∑︁

∑︁ −

𝑤 𝑗𝑙 𝑝ˆ 𝑗𝑙 + 𝑤 𝑗𝑖 𝑝 𝑗𝑖

𝑙∉{𝑖,𝑗 }

2 𝑤𝑙 𝑗 𝑝ˆ𝑙 𝑗 𝜋𝑙 + 𝑤𝑖 𝑗 𝑝ˆ𝑖 𝑗 𝜋𝑖

∑︁

√︃

20 log(𝑛) 𝑘

𝜆𝑛−1 (𝐿𝑊 )

,

which implies √ ∥𝒓 ∥ 2 ≤ 𝑛∥𝒓 ∥ ∞

𝑙∉{𝑖,𝑗 }

√︃ 10𝑛 log(𝑛)𝑝 16ℎ∥𝝅 ∥ ∞ √︁ √ 𝑘 ≤ 𝑛(1 + 2𝑛𝑝) . 𝑊) 𝜆 (𝐿 𝑛−1 −8

𝑤 𝑗𝑙 𝑝ˆ 𝑗𝑙 + 𝑤 𝑗𝑖 𝑝ˆ 𝑗𝑖

𝑙∉{𝑖,𝑗 }

4

1−𝑂 (𝑛 −9 )

′

1

2 𝑤𝑙 𝑗 𝑝ˆ𝑙 𝑗 𝜋𝑙 + 𝑤𝑖 𝑗 𝑝𝑖 𝑗 𝜋𝑖

16ℎ∥𝝅 ∥ ∞𝑛𝑝

′

4

1−𝑂 (𝑛

3 3 𝑤 𝑗𝑖 (𝑝ˆ 𝑗𝑖 − 𝑝 𝑗𝑖 ) 𝑤𝑖 𝑗 𝜋𝑖 (𝑝𝑖 𝑗 − 𝑝ˆ𝑖 𝑗 ) =Í + 𝜋¯ 𝑗 Í 𝑙∉{𝑖,𝑗 } 𝑤 𝑗𝑙 𝑝ˆ 𝑗𝑙 + 𝑤 𝑗𝑖 𝑝 𝑗𝑖 𝑙∉{𝑖,𝑗 } 𝑤 𝑗𝑙 𝑝ˆ 𝑗𝑙 + 𝑤 𝑗𝑖 𝑝 𝑗𝑖 𝑤𝑖 𝑗 𝜋 𝑗 (𝜋𝑖 − 𝜋 𝑗 + 𝜋 𝑗 − 𝜋¯ 𝑗 )(𝑝𝑖 𝑗 − 𝑝ˆ𝑖 𝑗 ) = Í 𝜋 𝑗 𝑙∉{𝑖,𝑗 } 𝑤 𝑗𝑙 𝑝ˆ 𝑗𝑙 + 𝑤 𝑗𝑖 𝑝 𝑗𝑖

)

Now we bound |𝜹 T 1𝑛 |. ∑︁

𝛿𝑖 ≤ ℎ𝑛

𝑖

b

∑︁ 𝑖

16

𝜋𝑖 𝛿 𝑖

𝑖

= ℎ𝑛

′

∑︁

𝜋ˆ𝑖 − 𝜋¯𝑖

Entrywise Error Bounds for Spectral Ranking with Semi-Random Adversaries

= ℎ𝑛

∑︁

√︃

≤ 4𝑛ℎ

𝑖

≤ ℎ𝑛∥𝝅 ∥ ∞

∑︁ Í

𝑗:𝑗≠𝑖 𝑤 𝑖 𝑗 (𝑝ˆ 𝑗𝑖 𝜋 𝑗 − 𝑝ˆ𝑖 𝑗 𝜋𝑖 )

𝜋𝑖

𝑖

Í

𝑖

≤ 2ℎ 2𝑛 1−𝑂 (𝑛 −9 )

𝑗:𝑗≠𝑖 𝑤 𝑖 𝑗 (𝑝ˆ 𝑗𝑖 𝜋 𝑗 − 𝑝ˆ𝑖 𝑗 𝜋𝑖 ) 𝜆𝑛−1 (𝐿𝑊 )

,

≤

and using Hoeffding’s inequality, √︂

1−𝑂 (𝑛 −8 )

!

40 log(𝑛)𝑝 𝑘  2 √︃ © 2 ∥𝝅 ∥ ∞𝑛 40 log(𝑛)𝑝 ª 𝑘 ­ ® ® ≥ 1 − 2 exp ­­− Í Í ® 2 2 ­ 𝑖 𝑗:𝑗≠𝑖 𝑤 𝑖 𝑗 (𝜋𝑙 + 𝜋 𝑗 ) /𝑘 ® 20𝑛 2 𝑝 log(𝑛) ≥ 1 − 2 exp − Í Í 2 𝑖 𝑗:𝑗≠𝑖 𝑤 𝑖 𝑗

¬

!

≥ 1 − 2 exp (−10 log(𝑛)) = 1 −

2 , 𝑛 10

thus √︃ |𝜹 T 1𝑛 | ≤ 2𝑛 2ℎ 2 ∥𝝅 ∥ ∞ 1−𝑂 (𝑛 −9 )

40 log(𝑛)𝑝 𝑘 . 𝜆𝑛−1 (𝐿𝑊 )

Therefore, 

 ∥𝒓 ∥ 2 |𝜹 T 1𝑛 | + √ 𝑛 𝜆 (𝐿𝑊 ) 1−𝑂 (𝑛 −9 ) 𝑛−1 𝝅   ∥𝒓 ∥ 2 |𝜹 T 1𝑛 | ≤ 2 2ℎ + √ ∥𝝅 ∥ ∞ 𝜆𝑛−1 (𝐿𝑊 ) 𝑛 √︃ √ √ 10𝑛 log(𝑛)𝑝 16ℎ 𝑛(1 + 2𝑛𝑝) 𝑘 ≤ 2 2ℎ 𝑊 )2 𝜆 (𝐿 𝑛−1 1−𝑂 (𝑛 −8 ) √︃ !

∥𝜹 ∥ 2 ≤ 2

+ 2𝑛ℎ 2 ∥𝝅 ∥ ∞

+

√︃

40𝑛 log(𝑛)𝑝 ! 𝑘 . 𝜆𝑛−1 (𝐿𝑊 )

8ℎ ∥𝝅 ∥ ∞ 𝜆𝑛−1 (𝐿𝑊 )

√︃ √︃ 40𝑛 log(𝑛)𝑝   32𝑝 20𝑛 log(𝑛) ∥𝝅 ∥ ∞ √ 𝑘 𝑘 2 𝑛𝑝 ∥𝝅 ∥ ∞ 4𝑛ℎ + 𝜆𝑛−1 (𝐿𝑊 ) 2 𝜆𝑛−1 (𝐿𝑊 ) √︃ 20 log(𝑛) ! 32ℎ𝑛𝑝 ∥𝝅 ∥ ∞ 𝑘 + 𝜆𝑛−1 (𝐿𝑊 ) √︃ √︃ 20 log(𝑛)𝑝 4𝑛𝑝 40 log(𝑛) 1024𝑛 2ℎ 3 𝑝 32ℎ 𝑘 𝑘 = + 𝜆𝑛−1 (𝐿𝑊 ) 3 𝜆𝑛−1 (𝐿𝑊 ) 2 √︃ 20 log(𝑛) 256ℎ 2𝑛𝑝 𝑘 + . 𝜆𝑛−1 (𝐿𝑊 ) 2 Finally, we have ∥ 𝝅ˆ − 𝝅 ∥ ∞ ∥𝝅 ∥ ∞ √︃ 40𝑛 log(𝑛)𝑝 8ℎ 𝑘 ≤ + ∥𝜹 ∥ ∞ 𝑊) 𝜆 (𝐿 𝑛−1 −9

P | g | ≤ ∥𝝅 ∥ ∞𝑛

«

2

∥𝝅 ∥ ∞

Next, since Í Í 𝑗 𝑤 𝑗𝑖 𝑝ˆ 𝑗𝑖 𝜋 𝑗 𝛿 𝑗 𝑗 𝑤 𝑗𝑖 𝑝ˆ 𝑗𝑖 ( 𝜋¯ 𝑗 − 𝜋 𝑗 ) Í Í 𝛿𝑖 = + ˆ 𝜋𝑖 𝑗 𝑤 𝑖 𝑗 𝑝 𝑖 𝑗 𝜋𝑖 𝑗 𝑤𝑖 𝑗 𝑝ˆ𝑖 𝑗 √︄ 8ℎ ª © ∑︁ 2 2 2 𝑤 𝑗𝑖 𝑝ˆ 𝑗𝑖 𝜋 𝑗 ∥𝜹 ∥ 2 + 𝑟𝑖 ® ≤ ­ ∥𝝅 ∥ ∞ 𝜆𝑛−1 (𝐿𝑊 ) −10 𝑗 1−𝑂 (𝑛 ) ¬ «

𝑗:𝑗≠𝑖 𝑤 𝑖 𝑗 𝑝ˆ𝑖 𝑗

g Í Í

20𝑛 log(𝑛) 𝑘 𝜆𝑛−1 (𝐿𝑊 ) 2

32𝑝

𝜋𝑖 − 𝜋¯𝑖

1−𝑂 (𝑛

)

𝑐3

𝑐1

√︂ √︂ √ √ 𝑛 log(𝑛)𝑝 16 10ℎ 2048 5ℎ 3 𝑛 4 log(𝑛)𝑝 3 + ≤ 𝑊 𝑘 𝑘 𝜆𝑛−1 (𝐿𝑊 ) 3 −7 𝜆𝑛−1 (𝐿 )

1−𝑂 (𝑛

)

𝑐2

√︂ √ √ 64 10ℎ 4 + 512 5ℎ 2 𝑛 2 log(𝑛)𝑝 2 + , 𝑘 𝜆𝑛−1 (𝐿𝑊 ) 2 completing the proof.

40𝑛 log(𝑛)𝑝 𝑘 𝜆𝑛−1 (𝐿𝑊 )

17

□