# sampling_for_beyondworstcase_online_ranking__0ded33bc.pdf

Sampling for Beyond-Worst-Case Online Ranking*

Qingyun Chen1, Sungjin Im1, Benjamin Moseley2, Chenyang Xu3, Ruilong Zhang4

1 Electrical Engineering and Computer Science, University of California at Merced 2 Tepper School of Business, Carnegie Mellon University 3 Shanghai Key Laboratory of Trustworthy Computing, East China Normal University 4 Department of Computer Science and Engineering, University at Buffalo qchen41@ucmerced.edu, sim3@ucmerced.edu, moseleyb@andrew.cmu.edu, cyxu@sei.ecnu.edu.cn, ruilongz@buffalo.edu

The feedback arc set problem is one of the most fundamental and well-studied ranking problems where n objects are to be ordered based on their pairwise comparison. The problem enjoys several efficient approximation algorithms in the offline setting. Unfortunately, online there are strong lower bounds on the competitive ratio establishing that no algorithm can perform well in the worst case. This paper introduces a new beyond-worst-case model for online feedback arc set. In the model, a sample of the input is given to the algorithm offline before the remaining instance is revealed online. This models the case in practice where yesterday s data is available and is similar to today s online instance. This sample is drawn from a known distribution which may not be uniform. We design an online algorithm with strong theoretical guarantees. The algorithm has a small constant competitive ratio when the sample is uniform if not, we show we can recover the same result by adding a provably minimal sample. Empirical results validate the theory and show that such algorithms can be used on temporal data to obtain strong results.

1 Introduction Finding a global ranking of items is a common problem faced in social network analysis, Bayesian learning, information aggregation, and game design (Bar-Yehuda et al. 1994; Baweja, Jia, and Woodruff 2022). The case where pairwise preference relationships are available for constructing the global ranking is referred to as Kemeny-Young Rank Aggregation (Kenyon-Mathieu and Schudy 2007a). For example, consider users that are playing an online game. Given the features of a user s playing history, it is possible to decide a preference on which of the two users should be ranked higher. However, the ranking may be inconsistent on three users due to the numerous features. The goal is to construct a global ranking that corresponds to a ranking of all users adhering to as many of the pairwise preferences. One of the oldest and most well-studied approaches for ranking is the Feedback Arc Set (FAS) problem in tournaments. In the FAS problem, there is a directed graph G = (V, E). Nodes represent objects to be ranked. There

*All authors (ordered alphabetically) have equal contributions and are corresponding authors. Copyright 2024, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.

is an edge between each pair of nodes that are directed, in which (u, v) implies v is better than u. The goal is to rank (i.e. order) the nodes in V so that the fewest number of edges are directed backward in the ordering. Equivalently, the goal is to reverse the direction of the smallest number of edges so that the graph has no directed cycles and thus admits a topological sort. A large number of applications of FAS have led to it being well-studied theoretically and empirically. The problem is NP-Hard (Alon 2006; Charbit, Thomass e, and Yeo 2007), and prior work has focused on approximation and heuristic algorithm design. Several constant approximation algorithms are known (Ailon, Charikar, and Newman 2008; Coppersmith, Fleischer, and Rudra 2006). Moreover, several scalable algorithmic approaches have been introduced for large data sets (Baweja, Jia, and Woodruff 2022; Im and Montazer Qaem 2020; Simpson, Srinivasan, and Thomo 2016a). While Feedback Arc Set is well understood offline and enjoys several good heuristic approaches, few results are known when items arrive over time. When items arrive over time, two possible models are the streaming and online settings. In the streaming setting, items come one at a time, and, using limited memory, the algorithm needs to construct a global ordering of the elements. The ordering can be changed as elements arrive; the challenge is that not all edges of the graph can be stored in memory. There has been a recent surge of interest in streaming algorithms (Baweja, Jia, and Woodruff 2022; Chen et al. 2021). In the online model, nodes arrive sequentially, revealing the directed edges connected to the nodes that have appeared earlier. The objective in this model is to continually provide a reliable approximation of the nodes that have surfaced so far. To delineate the model s goals more explicitly, the following criteria must be met: (1) At every moment, an ordered list of the nodes that have arrived thus far should be maintained. (2) The relative order of any subset of nodes should remain unchanged throughout the process. (3) The model should ensure an outcome of high quality when compared to the optimal offline solution. While this setting is natural; unfortunately, there is a Ω(n) lower bound on the competitive ratio; the proof is omitted in this version) in the worst-case online arrival model. In the worst-case model, the problem is too difficult to

The Thirty-Eighth AAAI Conference on Artificial Intelligence (AAAI-24)

solve online. Fortunately, practical applications are often more forgiving than these worst-case conditions. Take online ranking as an example; we frequently have access to a history of previous rankings. This historical data can be invaluable in constructing current and future rankings. In this paper, we model this pragmatic scenario as follows: The algorithm receives a sampling of nodes to be ranked, along with the edges among them. At the most basic level, this might involve a uniform sample, but our model can also accommodate non-uniform distributions. Subsequently, additional nodes requiring ranking will arrive online. This paper focuses on the question: can the presence of a sample effectively bypass worst-case lower bounds, thereby yielding beyond-worst-case robust results for online ranking?

1.1 Our Contributions This paper studies beyond worst-case online models for the feedback arc set problem. We first consider the pure online case where we show in Theorem 2 that any algorithm is Ω(n) competitive. Further, we show in Theorem 1 a matching upper bound by giving a O(n)-competitive algorithm. We then turn to beyond-worst-case models to overcome the strong lower bounds. In each model, the algorithm is given a (possibly non-uniform) sample S of the nodes and their pairwise edges. The remaining nodes arrive online in adversarial order. The sample represents data on past instances the algorithm has access to when solving a new online instance. We first consider a model introduced by Lattanzi et al. (Lattanzi et al. 2021) and further studied by Argue et al. (Argue et al. 2022). In this setting, the algorithm is given access to a uniform sample of the data. The goal is to show that the algorithm has strong performance on the remaining problem instance that arrives adversarially. In this model, we go beyond the worst-case lower bound and show that the algorithm has a constant competitive ratio when the sample is only a small λ faction of the items (Theorem 3). We also show that our ratio is essentially optimal (Theorem 4). We then introduce a new online model where we are given an initial sample, which is drawn from a distribution Q that is not necessarily uniform. Then the goal is for the algorithm to decide on a small sampling of the remaining nodes to ensure the algorithm has strong theoretical performance. Intuitively, the initial sample is easy to obtain, yet may be skewed. We want to correct the sample by adding a minimum-sized sample as it could be costly. We show in Theorem 5 an algorithm that can achieve a constant competitive ratio by sampling a small fraction of the remaining nodes even in the worst case.We show the optimality of the extra sample in terms of their size (Theorem 6). In the full version, we further extend our new model to the related correlation clustering problem and show that our algorithm is able to establish similar results. A summary of our theoretical results can be found in Table 1. These results give the first positive results for FAS in the online setting. We further validate the theory empirically by establishing that these algorithms have similar performance compared to offline algorithms that know the en-

tire input, even if the data is adversarially ordered. As strong evidence of the usefulness of the algorithmic ideas developed, we show that on temporal data where the sample is constructed based on the earliest arriving nodes, that the algorithms have minimal loss over the offline setting. This temporal model well captures the situation in practice where the sample corresponds to past data. 1.2 Related Work There are several known approximation algorithms for FAS. It is possible to achieve a (1 + ϵ) approximation in polynomial time (Ailon 2012; Kenyon-Mathieu and Schudy 2007a). It has been shown that a simple deterministic greedy algorithm is 5-approximated (Coppersmith, Fleischer, and Rudra 2010), i.e., order the vertices in increasing order of their indegrees where ties are broken arbitrarily. A popular randomized greedy algorithm is Pivot (also known as Kwiksort) which achieves a 3-approximation (Ailon, Charikar, and Newman 2008). When the underlying graph is not a tournament, (Even et al. 1998) gives a O(log n/ log log n)- approximation. Designing online algorithms models for beyond-worstcase analysis is a popular topic. Works such as (Lattanzi et al. 2020; Lykouris and Vassilvitskii 2021) have been investigating how to augment online algorithms with machinelearned predictions. Argue et al. (Argue et al. 2022), and Lattanzi et al. (Lattanzi et al. 2021) considered a similar model where the algorithm is given a random sample of the problem input and the rest of the input arrives in an adversarial order. In all of these cases, interesting algorithmic techniques and beyond-worst-case bounds emerge by allowing the algorithm to use extra information.

2 Preliminaries This paper considers the online version of the minimum feedback arc set problem. We first state the classical offline version of the problem for completeness. Definition 1 (Minimum Feedback Arc Set). We are given a tournament G := (V, E) with |V | = n, where a tournament is a directed graph G := (V, E) such that for each pair of vertices i, j V , either (i, j) E or (j, i) E. The goal is to find a permutation π on V minimizing the number of backward edges with respect to π. An edge (i, j) E is called a backward edge with respect to π if and only if π ranks j before i (denoted by j <π i). In the online setting, the vertices of the input graph arrive one by one. When a vertex arrives, its edges to all previous arrivals are released to the algorithm. The algorithm has to maintain an order of all arrived vertices at all times; that is, the algorithm must make an irrevocable decision upon each vertex arrival. The algorithm knows the size of the graph prior, i.e., the number of vertices is known by the algorithm. We show in Theorem 2 that the above online problem has a strong Ω(n) lower bound, where n is the number of vertices. We also provide an optimal algorithm for this fully online model. Theorem 2 suggests that obtaining any constant competitive ratio is impossible in the online model. Thus, we consider a semi-online model proposed by (Lattanzi et al. 2021).

The Thirty-Eighth AAAI Conference on Artificial Intelligence (AAAI-24)

Arrival Order Upper Bound Lower Bound Offline PTAS (Kenyon-Mathieu and Schudy 2007b) NP-Hard (Alon 2006) Adversarial O(n) (Theorem 1) Ω(n) (Theorem 2) Uniform Sample O( 1

λ) (Theorem 3) Ω( 1

λ) (Theorem 4) Extra Sample O(δ(Q, U)) (Theorem 5) Ω(δ(Q, U)) (Theorem 6)

Table 1: The summary of our results. Offline order refers to the classical FAS problem. Adversarial order is the standard worstcase setting. Uniform sample (formally termed semi-online; see Definition 2) is the model where the algorithm has access to a uniform random sample with λn vertices, and the remaining vertices arrive in adversarial order. Extra sampling (see Definition 3) corresponds to the new sampling model where we are given a set of vertices that are sampled from a predefined distribution Q, and the algorithm can do some extra sampling, before seeing the remaining vertices arriving adversarially. For simplicity, define δ(Q, U) as the total variance distance between distributions Q and U, where U is the uniform distribution.

Definition 2 (Semi-online Minimum Feedback Arc Set). In the semi-online setting, the vertices arrive in two phases: offline and online. In the first phase (offline phase), the algorithm is given a vertex set S V and its induced subgraph G[S]. The offline vertices S with |S| := λn are uniformly randomly sampled from V . In the online phase, the remainder of the vertices V \ S arrives online. When a vertex arrives, its edges to all previous arrivals are released to the algorithm. Upon each vertex s arrival, the algorithm must make an irrevocable position decision. The objective is to maintain an order of arrived vertices to minimize the number of backward edges.

For the semi-online setting, we show that a natural adaptation of the pivot algorithm proposed by (Ailon, Charikar, and Newman 2008) is essentially optimal. To make our results more robust, we extend the problem to the setting where the offline vertices may not be sampled by a uniform random distribution U. The adversary may sample vertices by some other distributions Q. Since distribution Q is input and can be arbitrary, it is impossible to get any positive result if we do not sample some extra vertices by the lower bound shown in Theorem 2. Thus, we are interested in how many extra vertices we need to sample to make the problem still admit a O( 1

λ)-competitive algorithm, i.e., recover the result obtained in the semi-online model.

Definition 3 (Extra Sampling Minimum Feedback Arc Set). In the offline phase, the algorithm is given a vertex set S V with E[|S|] := λn and its induced subgraph G[S], where the offline vertices S are sampled from V by a known distribution Q. And the algorithm is allowed to sample some extra vertices L from V by some distribution D, which is determined by the algorithm. In total, the algorithm can access the subgraph G[L S] in the offline phase. In the online phase, the remainder of the vertices V \ (L S) arrive online, and the algorithm must make an irrevocable position decision upon each vertex s arrival. The goal is to sample another set of vertices as less as possible such that the problem admits a O( 1

λ)-competitive algorithm.

3 Online Minimum Feedback Arc Set This section considers the online minimum feedback arc set problem under two settings: (i) Fully Online Model (Section 3.2): the adversary picks an arriving order of all vertices; (ii) Semi-online Model (Section 3.3): the algorithm is

allowed to uniform sample a subset S from V , and then the adversary picks an arriving order of vertices in V \ S. The algorithms for the two models share the same framework. The difference is that they access different vertex orders and thus obtain different competitive ratios. In the full online Model, the algorithm accesses an adversary order of all vertices while it combines a uniformly random order and adversary order in semi-online model. Our algorithm adapts the classical pivot algorithm proposed by (Ailon, Charikar, and Newman 2008). For completeness, we restate the algorithm in the full version of this paper. The performance of the pivot algorithm heavily depends on the order of vertices. It has been shown by (Ailon, Charikar, and Newman 2008) that it is 3-approximated when the order of vertices is uniformly random. In the online setting, the algorithm does not access the whole graph and thus cannot obtain a random order of vertices. The pivot algorithm can be naturally generalized to the online setting by considering the arriving order of vertices. However, the competitive ratio is no longer a simple constant in this case. As we will see in Section 3.2, the Pivot algorithm is O(n)- competitive when all vertices arrive in an adversary order. In contrast, we show in Section 3.3 that the competitive ratio is improved to O( 1

λ) when partial vertices arrive in random order.

3.1 Algorithmic Framework

For the convenience of analysis, we describe our algorithm as a binary tree construction algorithm. The binary tree construction is similar to the classical binary search tree construction. Given an order σ of all vertices, we construct a binary tree T iteratively. When t-th vertex (denoted by σ(t)) arrives, we check the direction of the edge between σ(t) and r (the root of the tree T). If (σ(t), r) E, then σ(t) goes to the left subtree; otherwise, it goes to the right subtree. We repeat the above process until we read in all vertices. The formal description can be found in Algorithm 1 and Algorithm 2. An example with vertex order σ := (v1, v2, v6, v3, v4, v5) can be found in Fig. 1. In the fully online model, Algorithm 1 takes the adversary order σ as the input; while in the semi-online model, Algorithm 1 takes σ := σS + σV \S as the input, where σS is a random order of vertices in S and σV \S is the adversary order of vertices in V \ S.

The Thirty-Eighth AAAI Conference on Artificial Intelligence (AAAI-24)

v5 v6 σS := (v1, v2) σV \S := (v6, v3, v4, v5)

σ := (v1, v2, v6, v3, v4, v5)

Figure 1: Illustration for the online pivot algorithm s processing. Suppose that S := { v1, v2 } and a uniform random order σS = (v1, v2). The adversary order for V \ S is σV \S = (v6, v3, v4, v5). Initially, the binary tree T is rooted by v1, and v2 is v1 s left child since (v2, v1) E. When v6 arrives, it will be inserted as the right child of v1 since (v1, v6) E. When v3 arrives, the algorithm will first determine whether it belongs to the left or right subtree of the tree rooted at v1. Since (v3, v1) E, v3 is part of the left subtree, and v3 will be inserted as v2 s left child since (v3, v2) E. After the construction, we get a binary tree shown in the right part. The inorder traversal is the algorithm s output, i.e., π = (v3, v2, v4, v1, v6, v5). Thus, there are three backward edges (v5, v4), (v4, v3) and (v6, v3) marked by dashed-lines in the original tournament. By our notation in Section 3.3, we have A = { ((v5, v4), (v4, v3), (v6, v3)) }. Moreover, by the definition of the lowest common ancestor, we have lca(v4, v5, T) = v1, lca(v3, v6, T) = v1 and lca(v3, v4, T) = v2. This implies that A(S) = A and A(V \ S) = .

Algorithm 1: Main Algorithm for Online Minimum Feedback Arc Set Input: An order σ := (v1, . . . , vn) of all vertices in V . Output: A permutation π : [n] [n] of all vertices in V . 1: T ; i 1 2: while i n do 3: Call construct-tree(T, r v1, vi). Insert vi to T rooted by r. 4: i i + 1. 5: end while 6: Let π be the inorder traversal of binary tree T. 7: return The vertex order π.

In the following, we present several concepts and observations which are helpful for the analysis in Section 3.2 and Section 3.3. The pivot algorithm analysis critically relies on Bad Triangle, which is defined in Definition 4.

Definition 4 (Bad Triangle). A bad triangle in G := (V, E) is a vertex set consisting of three vertices, denoted by t := { v1, v2, v3 }, such that they form a directed cycle, i.e., (v1, v2) E, (v2, v3) E and (v3, v1) E. Let T (G ) be all bad triangles in subgraph G G.

Intuitively, the number of bad triangles provides a lower bound of the optimal solution (Observation 1) and an upper bound of the algorithm s solution (Observation 2).

Observation 1. In any feasible solution, for any bad triangle t T (G), there must exist a backward edge in t.

Observation 2. Let A be the set of backward edges generated by Algorithm 1. Then, regardless of the vertices order, for each edge (i, j) A if and only if there exists a bad triangle t T (G) such that { i, j } t.

Algorithm 2: construct-tree(T, r, v)

Input: A binary tree T rooted by r and a vertex v. Output: A new binary tree T with v inserted. 1: if r = then 2: r v; Set up the root r of T. 3: end if 4: if (r, v) E then Insert to the right subtree. 5: u r s right child. 6: construct-tree(T, u, v). 7: end if 8: if (v, r) E then Insert to the left subtree. 9: ℓ r s left child. 10: construct-tree(T, ℓ, v). 11: end if

3.2 Fully Online Model Due to space limitations, we only state the two main theorems in the following and defer the proofs to the full version of this paper. The first theorem gives a O(n)-competitive algorithm, while the second one provides an Ω(n) lower bound to close the computational gap. Theorem 1. Algorithm 1 is O(n)-competitive when the vertices order is fully arbitrary. Theorem 2. There exists an instance distribution of the online feedback arc set problem where vertices arrive in adversarial order such that any randomized algorithm has a competitive ratio Ω(n), where n is the number of vertices.

3.3 Semi-online Minimum Feedback Arc Set In this section, we consider the semi-online minimum feedback arc set problem. The sample S is chosen from V uniformly at random, where |S| := λn.We mainly show the following.

The Thirty-Eighth AAAI Conference on Artificial Intelligence (AAAI-24)

Theorem 3. For the problem of semi-online minimum feedback arc set, there is a randomized algorithm that is O( 1

λ)- competitive, where λn is the number of vertices sampled in the offline phase. Moreover, any algorithm has a competitive ratio of Ω( 1

λ). Note that the vertex set S is uniformly randomly sampled from V in the current case. Recall that the input sequence of Algorithm 1 is σ := σS +σV \S, where σS is a random order of vertices in S and σV \S is the adversary order of vertices in V \ S. Notation and Analysis Framework. Let A E be the set of backward edges generated by Algorithm 1, and define ALG as the objective value of the algorithm, i.e., ALG := |A|. Use T to denote the binary tree constructed by the algorithm. Given a tree T and two vertices v1, v2 in the tree, the lowest common ancestor (denoted by lca(v1, v2, T)) of v1 and v2 is the lowest node in the tree T that has both v1 and v2 as descendants. Note that lca(v1, v2, T) is unique given the tree and two vertices. According to the property of our algorithm, we have the following observation. Observation 3. Let T be the binary tree constructed by Algorithm 1. For any backward edge (i, j) A, { i, j, lca(i, j, T) } forms a bad triangle. Now, we split A into two subsets A(S) and A(V \ S). A(S) is a set of backward edges that are separated by some vertices in S, i.e., A(S) := { (v, v ) A | lca(v, v , T) S }, while vertices in V \ S separate edges in A(V \ S), i.e., A(V \ S) := { (v, v ) A | lca(v, v , T) V \ S }. An example can be found in Fig. 1. Intuitively, for edges in A(S), we can charge them directly to the optimal solution by the classical analysis of the offline pivot algorithm. For edges in A(V \ S), we need more careful analysis to get rid of Ω(n) lower bound resulting from the adversary order of the vertices in V \ S. For notation consistency, define E[ALG(S)] := E[|A(S)|] and E[ALG(V \ S)] := E[|A(V \ S)|]. Clearly, E[ALG] = E[ALG(S)] + E[ALG(V \ S)]. Use OPT to denote the objective value of the optimal offline solution. The two terms ALG(S) and ALG(V \ S) are bounded by Lemma 1 and Lemma 2 respectively. Lemma 1. E[ALG(S)] 3 OPT. Lemma 2. E[ALG(V \ S)] 1

λ OPT. Combining Lemma 1 and Lemma 2, Theorem 3 directly follows. Due to space limits, we omit the two lemma s proofs in the paper. Remark. Our analysis leverages algorithmic and analysis ideas from previous work (Lattanzi et al. 2021; Mathieu, Sankur, and Schudy 2010) on correlation clustering. However, these two different problems lead to technical differences. The algorithms have similarities in that they recursively choose pivots, but the similarities stop there and the analysis requires considerably different techniques. In particular, the lower bounds used for the analysis are derived differently depending on the underlying problem structure and whether we include the sampled points or not. The detailed discussion can be found in the full version of the paper.

Hardness Result To complete our results, we build on the hard instance stated in Theorem 2 to give a lower bound of the semi-online model.Intuitively, we construct a large graph G := (V, E) with |V | := n and a vertex set T V with |T| := 1

λ such that the probability of each vertex in T being sampled by any algorithm is tiny. Then, by Theorem 2, any algorithm has competitive ratio Ω( 1

Theorem 4. In the semi-online model, any algorithm is Ω( 1

λ)-competitive for any λ (0, 1).

4 Extra Sampling Model

This section considers the extra sampling model. In the model, we access a predefined vertex subset S sampled from a distribution Q := {qv}v V , where each vertex v is sampled independently with a probability of qv and the expected number of the sampled vertices is λn. And then, the algorithm is allowed to sample some extra vertices. The goal is to make the extra sampling model still admit a O( 1

λ)- competitive algorithm. Use U := {pv = λ}v [n] to represent the uniform sampling distribution to represent that U is parameterized by λ, we may use Uλ. We show the following theorem.

Theorem 5. Given any predefined distribution Q and any parameter c (0, 1), there exists an algorithm that samples at most δ(Q, Uλ) extra vertices in expectation and achieves a competitive ratio of O( 1

c λ) with probability at least 1 e (1 c)2/2, where δ(Q, Uλ) is the total variance distance between the two distributions.

Letting the parameter c be a constant, Theorem 5 implies an algorithm which achieves O( 1

λ)-competitive with a constant probability. To close the computational gap of our problem, we further show the hardness results.

Theorem 6. Any O( 1

λ)-competitive algorithm must sample Ω(δ(Q, Uλ)) vertices in expectation.

Algorithmic Intuition. Based on the result stated in Theorem 3, we know that if the first λn arrivals satisfy the uniform random distribution, then Algorithm 1 is a O( 1

λ)- competitive algorithm. Thus, the main idea is to resample some vertices according to some distribution D such that the probability of each vertex being sampled is λ conditioned on whether it is in the predefined sample. Intuitively, we use D to rescale the probability of each vertex being sampled. Based on the distribution D, if we resample a vertex set L with |L| := λn vertices, then Algorithm 1 is a O( 1

λ)-competitive algorithm when the input sequence is σL + σV \L. Note that D may not be uniform, and thus, we are not able to ensure that L satisfies the cardinality constraint. But we can guarantee that |L| is O(λn) with high probability using a concentration bound. In summary, our algorithm mainly contains the following steps:

Given a predefined distribution Q and a vertex set S, construct a distribution D := (p1, . . . , pv). Sample a subset L by distribution D, i.e., for each v V , independently add v to L with probability pv.

The Thirty-Eighth AAAI Conference on Artificial Intelligence (AAAI-24)

Algorithm 3: Over-&Under-sampling Algorithm

Input: The distribution Q := (q1, . . . , qn) and the sampled vertex set S; Output: A sampling distribution D := (p1, . . . , pn). 1: for each vertex v V do 2: if qv < λ then Oversampling 3: if v S then pv 1; 4: else pv λ qv

1 qv . 5: end if 6: else (qv λ) Undersampling 7: if v S then pv λ

qv . 8: else pv 0. 9: end if 10: end if 11: end for 12: return D.

Run Algorithm 1 with the input sequence σL + σV \L, where σV \L is a vertex order given by the adversary. The crucial part of the algorithm is how to define the distribution D. The main idea is to oversample and undersample vertices based on distribution Q and the sampled vertex set S. Intuitively, if the sampled probability of a vertex in Q is larger than λ, we want to decrease (undersample) its probability in the constructed probability distribution; otherwise, we want to oversample. We construct a distribution D to sample each vertex with probability λ conditioned on Q to achieve this goal. To this end, we must carefully set parameters and distinguish several cases. The formal description can be found in Algorithm 3. Note that when the total variance distance δ(Q, U) is 0, i.e., the predefined distribution is exactly the uniform random distribution, the constructed distribution D is as follows: for each vertex v S, pv = 1; otherwise, pv = 0, which means that the vertex set sampled by D is still set S and no extra vertex is added. Then by Theorem 3, we know that Algorithm 1 is a O( 1

λ)-competitive algorithm. For an arbitrary distribution Q, the proof of Theorem 5 consists of two parts: (i) showing that the algorithm is O( 1

c λ)- competitive with a high probability, (ii) proving that the expected number of extra samples is δ(Q, U). Due to space limitations, we defer the proofs to the full version of this paper. We remark that the total variance distance δ(Q, U) is at most λ(1 λ)n.

Upper Bound of δ(Q, U). Note that P v V qv = λn since the expected size of the predefined sample set is λn. By some math, we see that P

v V :qv<λ(λ qv) is at most λ(1 λ)n. Moreover, when the total variance distance is λ(1 λ)n, the distribution Q is as follows:

Q = (1, . . . , 1 | {z } λn , 0, . . . , 0 | {z } (1 λ)n

5 Experiments This section validates the empirical performance of our sampling models on real datasets. We design two experiments.

First, we investigate the empirical performance of the semionline pivot algorithm (Algorithm 1) when we vary the size of the uniform sample. Second, we consider the extra sampling model and observe the algorithm s performance with and without extra samples.

5.1 Setup The experiments are conducted on a machine running Ubuntu 18.04 with an i7-7800X CPU and 48 GB memory. The experimental results are averaged over 10 runs. Datasets. Following the experimental setting introduced in (Simpson, Srinivasan, and Thomo 2016b), we use social network datasets to test the performance of the feedback arc set algorithms. The experiments consider three directed temporal network datasets with different sizes: College Msg1 (|V | = 1, 899, |E| = 59, 835), Math Overflow2 (|V | = 24, 818, |E| = 506, 550), and Reddit Hyperlink3 (|V | = 55, 863, |E| = 858, 490). Note that the networks are not complete graphs. Since the datasets are temporal and each vertex has a timestamp, we obtain complete graphs by adding all the missing edges and letting each of them point from the earlier released vertex to the other. Arrival Orders. The experiments investigate three arrival orders of vertices in the graphs. First of all, we consider the chronological order given by the data to simulate the performance of our sampling models in practice. Then we use the bad triangle decreasing order and the indegree decreasing order to approximate the adversarial order. In the bad triangle decreasing order, we compute the number of bad triangles that each vertex belongs to and let the vertex which is contained in more bad triangles arrive first, while the indegree decreasing order lets the vertex with a larger indegree arrive first.

5.2 Power of Uniform Sampling This experiment tests the performance of the pivot algorithm with different uniform sampling fractions λ s to show the power of uniform sampling. We consider λ {0, 0.001, 0.003, 0.027, 0.081, 0.243, 0.729, 1} and use the ratio of the algorithm s objective to the objective obtained by the offline pivot algorithm to illustrate the performance of the algorithm. For each dataset, we try the aforementioned three arrival orders. The results are shown in Fig. 2.

5.3 Power of Extra Sampling This experiment investigates the extra sampling model. To show the robustness of our extra-sampling algorithm, we let the predefined distribution be the most unfavorable one for the algorithm. To approximate such a sampling distribution under each arrival order, we let the predefined sample set always be the first λn arriving vertices; that is, the sampling probability of a vertex is 1 if the vertex is in the first λn vertices and 0 otherwise. Denote such a predefined sample set by Adv to imply that it is an adversarial-like sampling. Algorithm 3 then constructs a new sample Ours by discarding

1https://snap.stanford.edu/data/College Msg.html 2https://snap.stanford.edu/data/sx-mathoverflow.html 3https://snap.stanford.edu/data/soc-Reddit Hyperlinks.html

The Thirty-Eighth AAAI Conference on Artificial Intelligence (AAAI-24)

(a) College Msg

(b) Math Overflow

(c) Reddit Hyperlink

Figure 2: The experimental results on the three datasets when the sampling fraction λ varies. The x-axes and y-axes represent the sampling rate and the algorithm s objective relative to that of the pivot on the offline input, and they are both on the log scale.

(b) Bad Triangle Decreasing

(c) Indegree Decreasing

Figure 3: The performance of different sampling sets on College Msg when λ varies. The x-axe is on the log scale.

some and adding new to Adv. Further, to show the necessity of discarding some vertices in the predefined sample Adv, we also consider using all appearing in Adv and Ours, which is denoted as All. These three datasets give the same trends; thus, we show the results on one dataset in Fig. 3 and others appear in the full version of this paper.

5.4 Empirical Discussion The results show the following trends.

From Fig. 2, we see that on all of the datasets, even a small fraction of uniform samples can improve the performance significantly. Typically on the dataset Reddit Hyperlink, without any sample, the ratio is more than two hundred; while with only a sampling fraction of 0.1%, the ratio can be improved to single digits. From Fig. 3, we see the necessity of oversampling and undersampling. Having extra samples in addition to the predefined sample set gives a better performance (All). Discarding some according to our algorithm gives a further improvement (Ours).

6 Conclusion The paper considers online Feedback Arc Set (FAS) in tournaments in a beyond-worst-case manner. We show that it is

possible to break the pessimistic lower bound by giving a constant approximation for nodes arriving in the adversarial order, given access to a constant fraction of samples. We further investigate how to optimally exploit samples from skewed distributions and revisit the correlational clustering problem under the new model. These results take the first step towards studying various online ranking problems. We believe that the algorithmic ideas will be helpful to many other related problems in this area.

Acknowledgements Chenyang Xu is supported by the National Key Research Project of China under Grant No. 2023YFA1009402, the National Natural Science Foundation of China (No. 62302166), the Dean s Fund of Shanghai Key Laboratory of Trustworthy Computing, ECNU, and the Key Laboratory of Interdisciplinary Research of Computation and Economics (SUFE), Ministry of Education. Qingyun Chen and Sungjin Im are supported by NSF grants CCF-1844939 and CCF2121745. Benjamin Moseley is supported by a Google Research Award, an Infor Research Award, a Carnegie Bosch Junior Faculty Chair and NSF Grants CCF-2121744 and CCF-1845146. Ruilong Zhang is supported by NSF grant CCF-1844890.

The Thirty-Eighth AAAI Conference on Artificial Intelligence (AAAI-24)

References Ailon, N. 2012. An Active Learning Algorithm for Ranking from Pairwise Preferences with an Almost Optimal Query Complexity. J. Mach. Learn. Res., 13: 137 164. Ailon, N.; Charikar, M.; and Newman, A. 2008. Aggregating inconsistent information: Ranking and clustering. J. ACM, 55(5): 23:1 23:27. Alon, N. 2006. Ranking Tournaments. SIAM J. Discret. Math., 20(1): 137 142. Argue, C.; Frieze, A.; Gupta, A.; and Seiler, C. 2022. Learning from a Sample in Online Algorithms. In Oh, A. H.; Agarwal, A.; Belgrave, D.; and Cho, K., eds., Advances in Neural Information Processing Systems. Bar-Yehuda, R.; Geiger, D.; Naor, J.; and Roth, R. M. 1994. Approximation Algorithms for the Vertex Feedback Set Problem with Applications to Constraint Satisfaction and Bayesian Inference. In Sleator, D. D., ed., Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms. 23-25 January 1994, Arlington, Virginia, USA, 344 354. ACM/SIAM. Baweja, A.; Jia, J.; and Woodruff, D. P. 2022. An Efficient Semi-Streaming PTAS for Tournament Feedback Arc Set with Few Passes. In Braverman, M., ed., 13th Innovations in Theoretical Computer Science Conference, ITCS 2022, January 31 - February 3, 2022, Berkeley, CA, USA, volume 215 of LIPIcs, 16:1 16:23. Schloss Dagstuhl - Leibniz-Zentrum f ur Informatik. Charbit, P.; Thomass e, S.; and Yeo, A. 2007. The Minimum Feedback Arc Set Problem is NP-Hard for Tournaments. Comb. Probab. Comput., 16(1): 1 4. Chen, L.; Kol, G.; Paramonov, D.; Saxena, R.; Song, Z.; and Yu, H. 2021. Almost Optimal Super-Constant-Pass Streaming Lower Bounds for Reachability. Electron. Colloquium Comput. Complex., TR21-027. Coppersmith, D.; Fleischer, L.; and Rudra, A. 2006. Ordering by weighted number of wins gives a good ranking for weighted tournaments. In Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, 776 782. Coppersmith, D.; Fleischer, L.; and Rudra, A. 2010. Ordering by weighted number of wins gives a good ranking for weighted tournaments. ACM Trans. Algorithms, 6(3): 55:1 55:13. Even, G.; Schieber, B.; Sudan, M.; et al. 1998. Approximating minimum feedback sets and multicuts in directed graphs. Algorithmica, 20(2): 151 174. Im, S.; and Montazer Qaem, M. 2020. Fast and Parallelizable Ranking with Outliers from Pairwise Comparisons. In Machine Learning and Knowledge Discovery in Databases: European Conference, ECML PKDD 2019, W urzburg, Germany, September 16 20, 2019, Proceedings, Part I, 173 188. Springer. Kenyon-Mathieu, C.; and Schudy, W. 2007a. How to rank with few errors. In Johnson, D. S.; and Feige, U., eds., Proceedings of the 39th Annual ACM Symposium on Theory of Computing, San Diego, California, USA, June 11-13, 2007, 95 103. ACM.

Kenyon-Mathieu, C.; and Schudy, W. 2007b. How to rank with few errors. In STOC, 95 103. ACM. Lattanzi, S.; Lavastida, T.; Moseley, B.; and Vassilvitskii, S. 2020. Online Scheduling via Learned Weights. In Chawla, S., ed., Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, Salt Lake City, UT, USA, January 5-8, 2020, 1859 1877. SIAM. Lattanzi, S.; Moseley, B.; Vassilvitskii, S.; Wang, Y.; and Zhou, R. 2021. Robust Online Correlation Clustering. In Neur IPS, 4688 4698. Lykouris, T.; and Vassilvitskii, S. 2021. Competitive Caching with Machine Learned Advice. J. ACM, 68(4): 24:1 24:25. Mathieu, C.; Sankur, O.; and Schudy, W. 2010. Online Correlation Clustering. In STACS, volume 5 of LIPIcs, 573 584. Schloss Dagstuhl - Leibniz-Zentrum f ur Informatik. Simpson, M.; Srinivasan, V.; and Thomo, A. 2016a. Efficient Computation of Feedback Arc Set at Web-Scale. Proc. VLDB Endow., 10(3): 133 144. Simpson, M.; Srinivasan, V.; and Thomo, A. 2016b. Efficient Computation of Feedback Arc Set at Web-Scale. Proc. VLDB Endow., 10(3): 133 144.

The Thirty-Eighth AAAI Conference on Artificial Intelligence (AAAI-24)