# minimum_robust_multisubmodular_cover_for_fairness__95a551a6.pdf

Minimum Robust Multi-Submodular Cover for Fairness

Lan N. Nguyen My T. Thai Department of Computer and Information Science and Engineering University of Florida, Gainesville, Florida 32611 lan.nguyen@uﬂ.edu mythai@cise.uﬂ.edu

In this paper, we study a novel problem, Minimum Robust Multi-Submodular Cover for Fairness (MINRF), as follows: given a ground set V ; m monotone submodular functions f1, ..., fm; m thresholds T1, ..., Tm and a non-negative integer r, MINRF asks for the smallest set S such that for all i [m], min|X| r fi(S \ X) Ti. We prove that MINRF is inapproximable within (1 ϵ) ln m; and no algorithm, taking fewer than exponential number of queries in term of r, is able to output a feasible set to MINRF with high certainty. Three bicriteria approximation algorithms with performance guarantees are proposed: one for r = 0, one for r = 1, and one for general r. We further investigate our algorithms performance in two applications of MINRF, Information Propagation for Multiple Groups and Movie Recommendation for Multiple Users. Our algorithms have shown to outperform baseline heuristics in both solution quality and the number of queries in most cases.

Introduction In a minimum submodular cover, given a ground set V , a monotone submodular set function f : 2V R and a number T, the problem asks for a set S V of minimum size such that f(S) T. This problem was studied extensively in the literature because of its wide-range applications, e.g. data summarization (Mirzasoleiman et al. 2015; Mirzasoleiman, Zadimoghaddam, and Karbasi 2016), active set selection (Norouzi-Fard et al. 2016), recommendation systems (Guillory and Bilmes 2011), information propagation in social networks (Kuhnle et al. 2017), and network resilience assessment (Nguyen and Thai 2019; Dinh and Thai 2014). However, a single objective function f may not well model several practical applications where achieving multiple goals is required, especially when group fairness is considered. Let us consider the following two representative applications. Information Propagation in Social Network for Multiple Groups. Social networks are cost-effective tools for information spreading by selecting a set of highly inﬂuential people (called seed set) that, through the word-of-mouth effects, the information will be reached to a large number of population (Kuhnle et al. 2017; Nguyen, Zhou, and Thai 2019; Zhang et al. 2014; Nguyen, Thai, and Dinh 2016). For

Copyright 2021, Association for the Advancement of Artiﬁcial Intelligence (www.aaai.org). All rights reserved.

many applications (e.g. broadening participants in STEM), it is important to ensure the diversity and fairness among different ethnics and genders. Therefore, those applications aim to ﬁnd a minimum seed set such that the information can reach to each group in a fair manner. Items Recommendation for Multiple Users. Recommendation systems aim to make a good recommendation, e.g. a set of items, which can match users preferences. In many situations, an item can be served for multiple users, e.g. a family. In this problem, a user s utility level to a set of items is modelled under a monotone submodular function. The objective, therefore, is to ﬁnd the smallest set of items, from which we can design a recommendation for all users in a way that all reach a certain utility level. Additionally, these problems require robustness in the solution set, in the sense that the solution satisﬁes all the constraints even if some elements were removed. Those removal can be from various reasons. For instance, in information propagation, a subset of users may decide not to spread the information (Bogunovic et al. 2017). Or in recommendation systems, due to the uncertainty of underlying data, information of some items may not be accurate (Orlin, Schulz, and Udwani 2018). Achieving a reasonable prior distribution on the removed elements may not be practical in many situations. Or even when the distribution is known, it is critical to obtain a robust solution with a high level of certainty, in a way that all goals are still achieved under the worst-case removal. Motivated by that observation, in this work, we study a novel problem, Minimum Robust Multi-Submodular Cover for Fairness (MINRF), deﬁned as follows. Deﬁnition 1. (MINRF) Given a ﬁnite set V ; m monotone submodular functions f1, ...fm where fi : 2V R ; m non-negative numbers T1, ..., Tm, and a non-negative integer r, ﬁnd a set S V of minimum size such that i [m], min|X| r fi(S \ X) Ti. MINRF s objective can also be understood as ﬁnding S of minimum size such that for all X V that |X| r and i [m], fi(S \ X) Ti. Beside two applications as stated early, MINRF can also be applied in many other applications, such as Sensor Placement (Orlin, Schulz, and Udwani 2018; Ohsaka and Yoshida 2015), which guarantees each measurement (e.g. temperature, humidity) reaches a certain information gain while being robust against sensors failure;

The Thirty-Fifth AAAI Conference on Artificial Intelligence (AAAI-21)

or Feature Selection (Qian et al. 2017; Orlin, Schulz, and Udwani 2018), which aims for a smallest set of features that can retain information at a certain level while guaranteeing the set is not dependent on a few features. To solve MINRF, one direction is to list all constraints in a form of fi(. \ X) Ti |X| = r and i [m] and ﬁnd a smallest set that satisﬁes all those constraints. However, with large V , the amount of set X of size r is n r , making it impractical to enumerate all possible removed sets. Furthermore, we show that an algorithm, which is able to output a feasible solution to MINRF in general, is very expensive, requiring at least exponential number of queries in term of r. Even when r = 0, there exists no polynomial algorithm that can approximate MINRF within a factor of (1 ϵ) ln m unless P = NP. Thus solving MINRF remains open and to our knowledge, we are the ﬁrst one studying the problem. Contribution. Beside introducing MINRF and investigating the problem s hardness using complexity theory, we propose a bicriteria approximation algorithm, namely ALGR, to solve MINRF. ALGR s performance guarantee is tight to MINRF s inapproximability and required query complexity. To be speciﬁc, ALGR is polynomial with ﬁxed r and obtain S of size O(ln max(m,n)

α ) factor to the optimal solution where α (0, 1]. S guarantees that for all X V that |X| r and i [m], fi(S \ X) (1 α)Ti. In a special case of r = 1, we propose ALG1 which can run faster than ALGR. Both ALGR and ALG1 work in a manner that they frequently call an algorithm solving MINRF with r = 0 as a subroutine. Although MINRF with r = 0 has been studied in the literature, a new aspect of the problem requires us to propose new solutions to MINRF where r = 0. In particular, we propose Random Greedy (RANDGR) and re-investigate two existing algorithms, GREEDY and THRESGR, whose performance has been analyzed where fis receive values in Z, in order to adapt them to R domain. In comparison to GREEDY and THRESGR, RANDGR does not unite submodular functions into a single function; and introduces randomness to reduce queries to fis. RANDGR takes much fewer queries than GREEDY and THRESGR as shown in our experiments. Further, we investigate our algorithms performance on two applications of MINRF: Information Propagation for Multiple Groups and Movie Recommendation for Multiple Users. The experimental results show our algorithms outperformed some intuitive heuristics methods in both quality of solutions and the number of queries.

Preliminaries

Related Work

To our knowledge, this work provides the ﬁrst solutions to MINRF for a general r. In this part, we pay attention to recent studies on minimum multi-submodular cover (MINRF when r = 0), and robust submodular optimization. With minimum submodular cover (m = 1, r = 0), Goyal et al. (2013) showed that the classical greedy algorithm is able to obtain a bi-criteria ratio of O(ln α 1). If we run m instances of greedy, each with a constraint fi(.) Ti, get m output Si and returns i [m]Si, we can get the ratio of

O(m ln α 1) for MINRF when r = 0. In this paper, we aim for algorithms with better ratios. Krause et al. (2008) was the ﬁrst one proposing a problem of minimum multi-submodular cover; and the problem was then further studied by Mirzasoleiman, Zadimoghaddam, and Karbasi (2016); Iyer and Bilmes (2013). In general, their solution made a reduction from multiple submodular objectives to a single instance of a submodular cover problem by deﬁning F(.) = P i [m] min(fi(.), T) (all thresholds are the same); and ﬁnd S of minimum size such that F(S) = m T. Two algorithms were proposed, GREEDY (Krause et al. 2008; Iyer and Bilmes 2013) and THRESGR (Mirzasoleiman, Zadimoghaddam, and Karbasi 2016). Their performance analysis requires {fi}i [m] to receive values in Z to obtain ratio of O(ln maxe V F({e})). However, requiring {fi}i [m] to receive values in Z is not practical in many applications. In our work, we re-investigate GREEDY and THRESGR s performance without such requirement. Also, our RANDGR algorithm differs from such methods in which RANDGR does not unite objectives into a single function. Furthermore, RANDGR adds randomness to reduce the query complexity while still obtaining an asymptotically equal performance guarantee to that of GREEDY. With robust submodular optimization, the concept of ﬁnding set that is robust to the removal of r elements was ﬁrst proposed by Orlin, Schulz, and Udwani (2018). However, their problem is a maximization, namely Robust Submodular Maximization (RSM), deﬁned as follows: Given a ground set V , a monotone submodular function f, nonnegative integers k and r, ﬁnd S s.t |S| k that maximizes min Z A,|Z| r f(A \ Z). This problem was later studied further by Bogunovic et al. (2017); Mitrovic et al. (2017); Staib, Wilder, and Jegelka (2019); Anari et al. (2019). RSM and MINRF both focus on the worst-case scenario, where the removal of r elements has the greatest impact on the returned solution. Other than that, the two problems are basically different and we are unable to adapt existing algorithms for RSM to solve MINRF with performance guarantees. The key bottleneck preventing us to adapt those algorithms is how to guarantee that a returned solution is robust and satisﬁed submodular constraints.

Deﬁnitions & Complexity In this part, we present deﬁnitions and theories that would be used frequently in our analysis; and analyze complexity of solving MINRF. Due to page limit, detailed proofs of lemmas and theorems of this part are provided in Appendix. Deﬁnition 2. Given an instance of MINRF, including V, {fi}i [m], {Ti}i [m], a set A V is (t, α)-robust iff for all i [m], min|X| t fi(A \ X) (1 α)Ti. Speaking in another way, MINRF asks us to ﬁnd a minimum (r, 0)-robust set. Without loss of generality, in our algorithm, we change fi(.) := min(fi(.)/Ti, 1). It is trivial that fi is still monotone submodular; and MINRF s objective now is to ﬁnd S that min|X| r fi(S \ X) 1 i [m]. If there exists a (r, 0)-robust set, denote S as an optimal solution; and OPT(U, t) as a size of the minimum (t, 0)-

robust set that is a subset of U if there is any. So |S | = OPT(V, r). We have the following key lemma:

Lemma 1. For all X1, X2 V that |X1| = r1, |X2| = r2 and r1 + r2 r

OPT(V, r) OPT(V \ X1, r r1)

OPT V \ (X1 X2), r r1 r2

Lemma 1 is very critical and will be used frequently to obtain performance guarantees of our algorithms. Given a MINRF instance and α [0, 1], we aims to devise algorithms that guarantee:

If there exists (r, α)-robust sets in the MINRF instance, the returned solution is (r, α)-robust with size at most some factor to OPT(V, r).

Otherwise, the algorithms notify no (r, 0)-robust set exists.

We ﬁrst study the hardness of devising such an algorithm to solve MINRF. First, we show that: even the sub-task of outputting a (r, 0)-robust set if there is any, is already very expensive. That is stated in the following theorem.

Theorem 1. There exists no algorithm, taking fewer than exponential number of queries in term of r, is able to verify existence of a (r, 0)-robust set to MINRF.

Theorem 1 is proven by taking one instance of MINRF, in which the removal of any subset X V of a same size shows a similar behavior on the submodular objectives except for only one unique subset R of size r. The thresholds {Ti}i are set so that: if there exists a (r, 0)-robust set then V is the only (r, 0)-robust set and R is the only set that would make V \ R violate the constraints. Thus any algorithm, taking fewer than O( |V | r ) queries is unable to verify whether V is (r, 0)-robust. The full description of the MINRF instance is provided in Appendix. Furthermore, even there exists (r, 0)-robust sets, devising approximation algorithms for MINRF is NP-hard. We have the following theorem.

Theorem 2. There exists no polynomial algorithm that can approximate MINRF, even with r = 0, within a factor of (1 ϵ) ln m given ϵ > 0 unless P = NP.

Algorithms When r = 0 We ﬁrst study MINRF with r = 0 since complexity and solution quality of algorithms for MINRF with r = 0 play critical roles on the performance of ALG1 and ALGR. Although MINRF with r = 0 has been studied in the literature, these results cannot applied directly. The key barrier is that the initial solution set may not be empty. In this part, we propose RANDGR, a randomized algorithm with bicriteria approximation ratio of O(ln m

α ). Also, we re-investigate performance guarantees of GREEDY and THRESGR, extending from their performance when fis receive values in Z. With RANDGR, checking if there exists feasible solutions with r = 0 is quite trivial. RANDGR simply veriﬁes whether

Algorithm 1 RANDGR

Input V, S0, {fi}i [m]

1: if There exists i [m] s.t. fi(V ) < 1 α then 2: Return no feasible solution 3: t = 0; F0 = {fi}i [m] 4: while Ft = do 5: F = randomly select |Ft|/2 constraints from Ft 6: et = argmaxe V \St P fi F efi(St) 7: St+1 = St {et}; Ft+1 = Ft; t = t + 1 8: Remove all fi Ft that fi(St) 1 α out of Ft

fi(V ) 1 α for all i [m]. If no, the algorithm notiﬁes no feasible set exists and terminates. If there exists feasible solutions, RANDGR works in rounds in order to ﬁnd a (0, α)-robust solution. For each round, a new random process is introduced as follows: the algorithm randomly selects half of functions fis, each of which is still less than 1 α; and greedily chooses an element that maximizes the sum of marginal gains of the selected functions. This random process helps RANDGR (1) reduce the number of queries to fis by half at each round; and (2) establish a recursive relationship of obtained solutions at different rounds, which is critical for RANDGR to obtain its performance guarantee with high probability (w.h.p). RANDGR s pseudocode is presented by Alg. 1. In Alg. 1, St represents an obtained solution at round t and Ft is a set of fis that fj(St) 1 α fj Ft. Note that RANDGR starts with S0 as an input; and as can be seen later, RANDGR is used as a subroutine function in case r > 0, in which S0 may not be empty. Therefore, analyzing performance of RANDGR with S0 = is necessary and challenging. To obtain RANDGR s performance guarantee, we have the following lemma.

Lemma 2. At round t: E h P fi Ft+1 1 fi(St+1) i 1 1 2 OP T (V,0) P fi Ft 1 fi(St)

Lemma 2 establishes a recursive relationship between Ft and St at different rounds. This is a key to obtain RANDGR s approximation ratio. Assuming RANDGR stops after L rounds, L = |SL \ S0|. By using Markov inequality, we can bound L w.h.p to obtain RANDGR s performance guarantee as Theorem 3. Full proofs of Lemma 2 and Theorem 3 are presented in Appendix.

Theorem 3. Given an instance of MINRF with input V, {fi}i [m], S0 such that P

i [m] fi(S0) (1 η)m, and r = 0. If S is an output of RANDGR then w.h.p |S \ S0| OPT(V, 0)O(ln mη

α ) and each fi is queried at most O(|V |OPT(V, 0) ln mη

We now investigate the performance of GREEDY and THRESGR. Their performance guarantees are stated by Theorem 4 (GREEDY) and 5 (THRESGR). Due to page limit, their detailed description and proofs are presented in Appendix.

Theorem 4. Given an instance of MINRF with input V, {fi}i [m], S0 such that P i [m] fi(S0) (1 η)m, and r = 0. If GREEDY terminates with a (0, α)-robust solution S, then |S \ S0| OPT(V, 0)O(ln mη

α ) and each fi is queried at most O(|V |OPT(V, 0) ln mη

Theorem 5. Given an instance of MINRF with input V, {fi}i [m], S0 such that P i [m] fi(S0) (1 η)m, and r = 0. If THRESGR terminates with a (0, α)-robust solution S, then |S \ S0| OPT(V, 0)O( 1 1 γ ln mη

α ) where γ (0, 1) is the algorithm s parameter; and each fi is queried at most O( n

With S0 = , RANDGR, GREEDY and THRESGR (γ is close to 0) can obtain a ratio of O(ln m

α ), which is tight to the inapproximability of MINRF when r = 0 (Theorem 2).

Algorithms When r > 0 In this section, we propose two algorithms to solve MINRF when r > 0: ALG1 for a special case of r = 1 and ALGR for general r. Both algorithms frequently call an algorithm to MINRF when r = 0 as a subroutine, which could be either RANDGR, GREEDY or THRESGR as discussed earlier. In short, we use ALG0 to refer to any of these three. For simplicity, we ignore the step of notifying if there exists no (r, α) robust set in ALG1 and ALGR s description since it can trivially inferred from the outputs of ALG0. Without loss of generality, in our analysis, we assume there exists (r, 0)-robust sets.

Algorithm When r = 1 (ALG1) In general, ALG1 is an iterative algorithm, which iteratively checks if there exists an element whose removal causes an obtained solution S to violate at least one constraint. If such an element (let s call it e) exists, ALG1 gathers all violated constraints to form a new MINRF instance with r = 0, V \ {e} as an input ground set and S \ {e} as an initial set. This is a key of ALG1 because by solving that new MINRF instance using ALG0, ALG1 guarantees the obtained solution is robust against e s removal; and the algorithm can signiﬁcantly tighten an upper bound on the number of newlyadded elements in order to obtain a tight approximation ratio. ALG1 s pseudocode is presented by Alg. 2. In Alg. 2, S1 is a (0, α)-robust set, found by using ALG0 with the original MINRF s input (line 1). S, returned by ALG1, is (1, α)-robust because:

For any e S1 that violates the condition of while loop (line 2), ALG1 guarantees fi(S \ {e}) 1 α (output of ALG0, line 4).

For any e S1, as S1 S \ {e}, we have fi(S \ {e}) fi(S1) 1 α (output of ALG0, line 1).

Denote E as a set of e S1 that violate the condition of while loop (line 2). For each e E, denote Se as S right before e is considered by the while loop of line 2. Let ρe = P i efi(Se\{e})/m. To obtain ALG1 s performance guarantee, we have the following lemma.

Lemma 3. P e E ρe 1

Algorithm 2 Algorithm when r = 1 (ALG1)

Input V, {fi}i [m]

1: S = S1 = ALG0 (V, , {fi}i [m]) 2: while e S1 that i [m], fi(S \ {e}) < 1 α do 3: F = set of all fi that fi(S \ {e}) < 1 α 4: S = ALG0 (V \ {e}, S \ {e}, F ) 5: S = S S

Proof. Let s sort elements in S1 = {u1, u2, ...} in the order of being added into S1 by ALG1 (line 1). Let Se 1 = {u1, ..., ue 1}. Due to submodularity, P i efi(Se 1) P i efi(S \ {e}) = ρem. Then: X

i efi(Se 1) X

i efi(Se 1) m

which means P e E ρe 1 and the proof is completed.

We then obtain ALG1 s performance guarantee as stated in Theorem 6. Theorem 6. Given an instance of MINRF with input V, {fi}i [m] and r = 1. If S is an output of ALG1 and S1 is a (0, α)-robust set outputted by ALG0(V, , {fi}i [m]) then |S| OPT(V, 1)O(|S1| ln m + 1/α).

Proof. From a ratio of ALG0 and lemma 1, we have |S1| O(ln m

α )OPT(V, 0) O(ln m

α )OPT(V, 1). For each e E and Se as deﬁned before, we have: X

i fi(Se \ {e}) = X

i fi(Se) ρem m(1 α ρe)

The last inequality comes from the fact that S1 Se and S1 is (0, α)-robust. Then, with S = ALG0 (V \ {e}, Se \ {e}, F ) in line 4, denote δSe = S \ Se. From the ratio of ALG0 and lemma 1, we have:

|δSe| O(ln (α + ρe)m

α )OPT(V \ {e}, 0)

O(ln (α + ρe)m

α )OPT(V, 1)

Therefore, with S is the returned solution, we have:

|S| = |S1| + X

e E ln (α + ρe)m

α|E| |E| OPT(V, 1)

α + ln m(1 + 1 α|E|) |E| OPT(V, 1)

O(|E| ln m + 1

α)OPT(V, 1)

Algorithm 3 Algorithm with general r (ALGR)

Input V, {fi}i [m], r

1: F0 = {fi}i [m]; S0 = ALG0 (V, , F0); 2: for t = 1 r do 3: Ft = 4: for each set X St 1 that |X| = r, X St 2 do 5: for each i [m] s.t. fi(St 1 \ X) < 1 α do 6: Deﬁne fi,X(.) = fi(. \ X) 7: Ft = Ft {fi,X}

8: St = ALG0 (V, St 1, Ft)

which completes the proof.

ALG1 s ratio is tight by considering a special instance of MINRF, Robust Set Cover with r = 1. This tight example is provided in Appendix. In term of query complexity, it is trivial that if ALG1 uses RANDGR or GREEDY as ALG0, each fi would be queried at most O(n max(OPT(V, 1)(|S1| ln m + 1/α), n)) times. If THRESGR is used, each constraint of F in line 4 is queried at most O(n ln mn) times, thus each fi is queried at most O(n|S1| ln mn) times in total.

Algorithm For General r (ALGR)

ALGR works in at most r rounds, in which after t rounds, ALGR guarantees an obtained solution is (t, α)-robust. Denote St as the obtained solution after t rounds. At round t, ALGR introduces a new MINRF instance with a new set of functions Ft. Each function in Ft is deﬁned by a function fi and a set X St that fi(St \ X) < 1 α and |X| = r. This is a key of ALGR because by solving the new MINRF instance to obtain St+1, RANDGR guarantees St+1 is (t, α)- robust. Also the algorithm is able to bound the number of newly-added elements in term of |S | by observing that S is also a feasible solution to the new MINRF instance. ALGR s pseudocode is presented by Alg. 3. Note that ALGR guarantees Sr is (r, α)-robust without a need of scanning all the removals of its subsets of size r. We prove that by using contradiction as follows: Assume Sr is not (r, α)-robust, then there exists X V and fi such that |X| = r and fi(Sr \ X) < 1 α. Let X0 = X S0, and Xt = X (St \ St 1) for t = 1 r. If there exists an empty Xt, let X = t 1 i=0Xi. We have |X | r and X St 1. Due to the output of ALG0 in line 8, fi(St \ X ) 1 α. But St \ X Sr \ X, so fi(Sr \ X) 1 α, which contradicts to our assumption. Thus, no Xt should be empty, which is impossible since |X| = r | r t=0Xt|, and X0, ..., Xr are disjoint. Therefore, Sr should be (r, α)-robust. To obtain ALGR s performance guarantee, we have the following lemma.

Lemma 4. |St \St 1| O(ln |Ft|

α )OPT(V, r) for all t r

Proof. Considering a new constraint fi,X created in line 6, it is trivial that the function fi,X is monotone submodular. Also, as S is (r, 0)-robust, fi,X(S ) = fi(S \ X) 1. That means S is feasible for the MINRF instance in line 6, with Ft as a set of constraint and r = 0. The lemma follows from the ratio of ALG0.

Lemma 4 is critical to obtain ALGR s ratio, stated in the following theorem. Theorem 7. Given an instance of MINRF with input V, {fi}i [m], r, if S is an output of ALGR, then:

|S| OPT(V, r)O(r ln m/α + r2 ln n)

Proof. Using lemma 1 and ALG0 s ratio, we have: |S0| OPT(V, 0)O(ln m/α) OPT(V, r)O(ln m/α). Therefore, from lemma 4, we have:

|Sr| = |S0| +

t=1 |St \ St 1|

t=1 ln |Ft|

α ) OPT(V, r)

Furthermore, Pr t=1 |Ft| m |Sr 1| r because: (1) No subset X Sr 1 of size r is considered more than one round (line 2) as if fi(St \ X) 1 α then fi(St+1 \ X) 1 α; and (2) each subset X added to Ft at most m new constraints. Therefore, by using AM-GM inequality, we have: Q t |Ft| (

r n r )r. Thus, |Sr| O(r ln m

α + r2 ln n) OPT(V, r).

Query Complexity. The bottleneck of ALGR is from the task of ﬁnding all subsets X in line 4. As there is |Sr 1| r subsets X, ALGR takes |Sr 1| r queries for each fi to only ﬁnd X; and in the worst case, each fi will generate |Sr 1| r functions fi,X (line 6). Then, if ALGR uses RANDGR or GREEDY as ALG0, in worst case, each fi is queried at most O(n(r ln m

α + r2 ln n) OPT(V, r) |Sr 1| r ) times. If THRESGR is used, at round t, each fi is queried at most O( n|Ft|

α ). Overall, ALGR using THRESGR

will query each fi at most O( n

γ |Sr 1| r (r ln m

α + r2 ln n)) times. ALGR is polynomial with ﬁxed r and favourable if OPT(V, r) n.

Experimental Evaluation In this section, we compare our algorithms with existing methods and intuitive heuristics on two applications of MINRF, Information Propagation for Multiple Groups (IP) and Movie Recommendation for Multiple Users (MR). The source code is available at https://github.com/lannn2410/minrf. Information Propagation for Multiple Groups (IP) In this problem, a social network is modeled as a directed graph G = (V, E) where V is a set of social users. Each edge (u, v) is associated with a weight wu,v, representing the strength of inﬂuence from user u to v. To model the information propagation process, we use Linear Threshold (LT) Model (Kempe, Kleinberg, and Tardos

0.6 0.65 0.7 0.75 0.8 0.85 0.9

0.6 0.65 0.7 0.75 0.8 0.85 0.9

# queries (IP)

# queries (MR)

RANDGR GREEDY THRESGR SEP

Figure 1: Performance of algorithms with r = 0

2003; Nguyen and Thai 2020). In general, the process is as follows: Each v V has a threshold θv chosen uniformly at random in [0, 1] and the information start from a seed set S V . At ﬁrst all users in S become active. Next, information cascades in discrete steps and in each step, a user v becomes active if P active u wu,v θv. The process stops when no more user can become active. Given a collection U of subsets of V , i.e U = {C1, ..., Cm} where Ci V . Each Ci represents a group that we need to inﬂuence. Denote Ii(S) as the expected number of active users in Ci by a seed set S. Given a number T [0, 1], IP aims to ﬁnd the smallest S such that for all Ci U, min|X| r Ii(S \ X) T|Ci|. We use Facebook dataset from SNAP database (Leskovec and Krevl 2014), an undirected graph with 4,039 nodes and 88,234 edges. Since it is undirected, we treat each edge as two directed edges. The weight wu,v is set to be 1/dv where dv is in-degree of v. U is a collection of groups to which users are classiﬁed based on their gender or race. Due to lack of data information, a user s race and gender are randomly assigned. Ii(S) is estimated over 100 graph samples. Movie Recommendation for Multiple Users (MR) In this problem, given a set M of movies, a set U of users, each user u has a list Lu of his/her favourite movies. Given S U, a utility score of u to S is deﬁned as fu(S) = P i Lu;j S\Lu si,j (Mirzasoleiman, Zadimoghaddam, and Karbasi 2016) where si,j [0, 1] which measures the similarity between movie i and j. Given a number T, the objective is to ﬁnd the smallest set of movies to recommend to all users in a way such that every user s utility level is at least T under any r inaccurate-data movies removal, i.e. min|X| r fu(S \ X) T for all u U. We use Movie Lens dataset from Group Lens (2015) database, which includes information of 10,381 movies; and their 20,000,264 ratings (ranging in [0, 5]) from 138,493 users. We randomly pick 4 users for a set U, Lu contains movies that u rated at least 4. Each movie i is associated by a 1,129-dimension vector vi, where each entry (ranging in [0, 1]) represents the relevant score between the movie and a keyword. The relevant scores are available in the dataset. We use cosine similarity score vi vj vi vj to present si,j. For each user u, fu(S) is normalized to be in range [0, 1].

Compared Algorithms With r = 0, we compare RANDGR, GREEDY and THRESGR (γ = 0.2) with SEP algorithm: which considers each constraint separately, runs greedy to ﬁnd a set Si that fi(Si) 1 α and return i [m]Si. SEP obtains a ratio of O(m ln 1

α). With r > 0, we compare ALGR s performance in combination with each ALG0, including RANDGR, GREEDY, THRESGR, SEP. Each combination of ALGR to a ALG0 algorithm is denoted, in short, ALGR-name of the ALG0 algorithm, e.g. ALGR-RANDGR. We also compare ALGR with DISJOINT, a heuristic we propose to evaluate. DISJOINT ﬁnds r + 1 disjoint sets S1, ..., Sr+1 such that fi(Sj) 1 α for all i [m] and j [r + 1]; and returns S = j [r+1]Sj. If DISJOINT successfully ﬁnds all {Sj}j [r+1], then S is feasible to MINRF without the need for checking all subsets of size r. This is because for any set X of size r, there should exist Sj that Sj X = . Thus, Sj S \ X, which means fi(S \ X) fi(Sj) 1 α for all i [m]. However, there are two problems with DISJOINT: (1) If DISJOINT cannot ﬁnd all {Sj}j [r+1], the algorithm does not guarantee there exists no feasible solution to MINRF; and (2) DISJOINT does not obtain any approximation ratio. For r = 1, we also evaluate ALG1 performance in combination with each ALG0 algorithm, including RANDGR, GREEDY, THRESGR. Other. We set α = 0.1. Results are averaged over 10 repetitions.

Experimental Results Fig. 1 shows the performances of different ALG0 algorithms in comparison with SEP. We can see that ALG0 algorithms totally outperformed SEP in solution quality by a huge margin. RANDGR returned solutions approximately close to GREEDY, which is the best one in term of solution quality. However, in term of query efﬁciency, RANDGR took much fewer queries than GREEDY and; and was the fastest algorithm in the IP problem. This conﬁrms the efﬁciency of RANDGR by introducing randomness and discarding satisﬁed constraints after each iteration. Fig. 2 shows algorithms performance on the IP and MR problems when r = 1. The two proposed heuristics, ALG1SEP and DISJOINT, showed the worst performance in solu-

0.6 0.65 0.7 0.75 0.8 0.85 0.9 20

0.6 0.65 0.7 0.75 0.8 0.85 0.9

# queries (IP)

# queries (MR)

ALG1 RANDGR ALG1 GREEDY ALG1 THRESGR ALGR SEP ALGR RANDGR ALGR GREEDY ALGR THRESGR DISJOINT

Figure 2: Performance of algorithms with r = 1

# queries (IP)

# queries (MR)

ALGR RANDGR ALGR GREEDY ALGR THRESGR ALGR SEP DISJOINT

Figure 3: Performance of algorithms with various r

tion quality. DISJOINT s undesirable performance came from the fact that a union of disjoint subsets, each is able to satisfy all constraints, is not a necessary condition to guarantee robustness. Also, by ﬁnding disjoint subsets, DISJOINT needed more queries than any other algorithms. In combination with the same ALG0 algorithm, ALG1 and ALGR had almost similar returned solution but ALG1 totally outperformed ALGR in term of number of queries. That can be explained by the fact that whenever ALG1 ﬁnds an element e whose removal violates at least one constraint, ALG1 will add elements to compensate for e s removal. That guarantees not only S is robust to e s removal but also the newly-added elements may help S being robust against some other elements removal as well. On the other hand, ALGR gathers all elements, each element s removal violates at least one constraint, to form a new MINRF instance with a much larger set of submodular functions than ALG1. That helps ALG1 obtain better number of queries than ALGR. Fig. 3 shows algorithms performance with larger r. We observed that ALGR-SEP and DISJOINT were outperformed by other algorithms by a huge margin in solution quality; but took much fewer number of queries than the others. That is because with larger r, the number of subsets of size r is increased by an exponent rate in term of r, which increases signiﬁcantly the number of queries of ALGR for scanning subsets of size r of Sr 1. SEP was less suffered than our ALG0 algorithms because SEP returned much larger solu-

tions, which can reach robustness at St where t r. On the other hand, DISJOINT had the small number of queries because DISJOINT does not need to scan all removals of its subsets of size r to check feasibility of the returned solution. Fig. 3 also shows that: ALGR-RANDGR performed the best in both solution quality and the number of queries in comparison with ALGR-GREEDY and ALGR-THRESGR. Although THRESGR was the most efﬁcient ALG0 algorithm when r = 0 (standalone) or r = 1 (combining with ALG1 or ALGR), ALGR-THRESGR s performances were undesirable with large r. This is because THRESGR tends to return larger solution than RANDGR and GREEDY. Therefore, ALGRTHRESGR requires more queries to scan over all subset of size r of Sr 1 than ALGR-RANDGR and ALGR-GREEDY.

Motivated by real-world applications, in this work, we studied a problem of minimum robust set subject to multiple submodular constraints, namely MINRF. We investigate MINRF s hardness using complexity theories; and proposed multiple approximation algorithms to solve MINRF. Our algorithms are proven to return tight performance guarantees to MINRF s inapproximability and required query complexity. Finally, we empirically demonstrated that our algorithms outperform several intuitive methods in terms of the solution quality and number of queries.

Acknowledgements

This work was supported in part by the National Science Foundation (NSF) grants IIS-1908594, IIS-1939725, and the University of Florida Informatics Institute Fellowship Program. We would like to thank the anonymous reviewers for their helpful feedback.

Anari, N.; Haghtalab, N.; Naor, S.; Pokutta, S.; Singh, M.; and Torrico, A. 2019. Structured Robust Submodular Maximization: Ofﬂine and Online Algorithms. In The 22nd International Conference on Artiﬁcial Intelligence and Statistics, 3128 3137.

Bogunovic, I.; Mitrovi c, S.; Scarlett, J.; and Cevher, V. 2017. Robust submodular maximization: A non-uniform partitioning approach. In Proceedings of the 34th International Conference on Machine Learning-Volume 70, 508 516. JMLR. org.

Dinh, T. N.; and Thai, M. T. 2014. Network under joint node and link attacks: Vulnerability assessment methods and analysis. IEEE/ACM Transactions on Networking 23(3): 1001 1011.

Goyal, A.; Bonchi, F.; Lakshmanan, L. V.; and Venkatasubramanian, S. 2013. On minimizing budget and time in inﬂuence propagation over social networks. Social network analysis and mining 3(2): 179 192.

Group Lens. 2015. Movie Lens 20M Dataset. https:// grouplens.org/datasets/movielens/20m/.

Guillory, A.; and Bilmes, J. A. 2011. Simultaneous learning and covering with adversarial noise .

Iyer, R. K.; and Bilmes, J. A. 2013. Submodular optimization with submodular cover and submodular knapsack constraints. In Advances in Neural Information Processing Systems, 2436 2444.

Kempe, D.; Kleinberg, J.; and Tardos, E. 2003. Maximizing the spread of inﬂuence through a social network. In Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, 137 146. ACM.

Krause, A.; Mc Mahan, H. B.; Guestrin, C.; and Gupta, A. 2008. Robust submodular observation selection. Journal of Machine Learning Research 9(Dec): 2761 2801.

Kuhnle, A.; Pan, T.; Alim, M. A.; and Thai, M. T. 2017. Scalable bicriteria algorithms for the threshold activation problem in online social networks. In IEEE INFOCOM 2017-IEEE Conference on Computer Communications, 1 9. IEEE.

Leskovec, J.; and Krevl, A. 2014. SNAP Datasets: Stanford Large Network Dataset Collection. http://snap.stanford.edu/ data.

Mirzasoleiman, B.; Karbasi, A.; Badanidiyuru, A.; and Krause, A. 2015. Distributed submodular cover: Succinctly summarizing massive data. In Advances in Neural Information Processing Systems, 2881 2889.

Mirzasoleiman, B.; Zadimoghaddam, M.; and Karbasi, A. 2016. Fast distributed submodular cover: Public-private data summarization. In Advances in Neural Information Processing Systems, 3594 3602. Mitrovic, S.; Bogunovic, I.; Norouzi-Fard, A.; Tarnawski, J. M.; and Cevher, V. 2017. Streaming robust submodular maximization: A partitioned thresholding approach. In Advances in Neural Information Processing Systems, 4557 4566. Nguyen, H. T.; Thai, M. T.; and Dinh, T. N. 2016. Stopand-stare: Optimal sampling algorithms for viral marketing in billion-scale networks. In Proceedings of the 2016 International Conference on Management of Data, 695 710. ACM.

Nguyen, L.; and Thai, M. T. 2020. Streaming k-Submodular Maximization under Noise subject to Size Constraint. In International Conference on Machine Learning, 7338 7347. PMLR. Nguyen, L. N.; and Thai, M. T. 2019. Network Resilience Assessment via Qo S Degradation Metrics: An Algorithmic Approach. Proceedings of the ACM on Measurement and Analysis of Computing Systems 3(1): 1 32. Nguyen, L. N.; Zhou, K.; and Thai, M. T. 2019. Inﬂuence maximization at community level: A new challenge with nonsubmodularity. In 2019 IEEE 39th International Conference on Distributed Computing Systems (ICDCS), 327 337. IEEE. Norouzi-Fard, A.; Bazzi, A.; Bogunovic, I.; El Halabi, M.; Hsieh, Y.-P.; and Cevher, V. 2016. An efﬁcient streaming algorithm for the submodular cover problem. In Advances in Neural Information Processing Systems, 4493 4501.

Ohsaka, N.; and Yoshida, Y. 2015. Monotone k-submodular function maximization with size constraints. In Advances in Neural Information Processing Systems, 694 702. Orlin, J. B.; Schulz, A. S.; and Udwani, R. 2018. Robust monotone submodular function maximization. Mathematical Programming 172(1-2): 505 537. Qian, C.; Shi, J.-C.; Yu, Y.; Tang, K.; and Zhou, Z.-H. 2017. Subset selection under noise. In Advances in neural information processing systems, 3560 3570.

Staib, M.; Wilder, B.; and Jegelka, S. 2019. Distributionally Robust Submodular Maximization. In The 22nd International Conference on Artiﬁcial Intelligence and Statistics, 506 516. Zhang, H.; Mishra, S.; Thai, M. T.; Wu, J.; and Wang, Y. 2014. Recent advances in information diffusion and inﬂuence maximization in complex social networks. Opportunistic Mobile Social Networks 37(1.1): 37.