--- title: "An Efficient Evolutionary Algorithm for Minimum Cost Submodular Cover" authors: - "Victoria G. Crawford" doi: "10.24963/ijcai.2019/171" url: "https://ijcai.org/proceedings/2019/171" pdf: "https://ijcai.org/proceedings/2019/0171.pdf" venue: "Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence" year: 2019 pages: "1227-1233" track: "Main track" keywords: - "Heuristic Search and Game Playing: Combinatorial Search and Optimisation" - "Heuristic Search and Game Playing: Heuristic Search and Machine Learning" --- # An Efficient Evolutionary Algorithm for Minimum Cost Submodular Cover Victoria G. Crawford *Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence*, pages 1227-1233. DOI: [10.24963/ijcai.2019/171](https://doi.org/10.24963/ijcai.2019/171) ## Abstract In this paper, the Minimum Cost Submodular Cover problem is studied, which is to minimize a modular cost function such that the monotone submodular benefit function is above a threshold. For this problem, an evolutionary algorithm EASC is introduced that achieves a constant, bicriteria approximation in expected polynomial time; this is the first polynomial-time evolutionary approximation algorithm for Minimum Cost Submodular Cover. To achieve this running time, ideas motivated by submodularity and monotonicity are incorporated into the evolutionary process, which likely will extend to other submodular optimization problems. In a practical application, EASC is demonstrated to outperform the greedy algorithm and converge faster than competing evolutionary algorithms for this problem. ## Full text ## 1 Introduction A function f : 2S → R≥0 defined on subsets of a ground set S is monotone submodular if it possesses the following two properties: - i. For all A ⊆ B ⊆ S, f(A) ≤ f(B) (monotonicity). Monotone submodular set functions and optimization problems are found in many applications in machine learning and data mining. In this paper, the NP-hard Minimum Cost Submodular Cover Problem (MCSC) is considered, which is defined as follows. Problem1 (MinimumCost Submodular Cover (MCSC)). Let S be a ground set of size n. Let c : 2S → R≥0 be a modular 1 function such that c(X) = 0 if and only if X = ∅, and f : 2S → R≥0 be monotone submodular. Given a threshold τ ≤ f(S), MCSC is to find argmin{c(X) : X ⊆ S, f(X) ≥ τ}. The function c is called the cost, while f is called the benefit. 1 The function c is modular if c(X) = ∑x∈X c({x}) for all X ⊆ S. Applications of MCSC include data summarization [Mirzasoleiman et al., 2015; 2016], active set selection [Norouzi-Fard et al., 2016], recommendation systems [Guillory and Bilmes, 2011], and viral marketing in social networks [Kuhnle et al., 2017]. The standard greedy algorithm 2 is an effective, efficient approximation algorithm for MCSC [Wolsey, 1982]; however, once the greedy solution has been obtained, it is unclear how it could be improved if more computational resources are available. Therefore, it is of interest to employ methods that can improve the solution quality at the expense of more runtime, while maintaining a worst-case guarantee. For this reason, an evolutionary algorithm has recently been proposed for MCSC [Qian et al., 2015a]. Although random search methods such as evolutionary algorithms (EA) can find better quality solutions in practice, it is difficult to analyze the approximation quality of evolutionary algorithms. The algorithm of Qian et al. is able to improve upon the greedy solution in practice, but requires expected exponential time 3 to have a worst-case guarantee similar to that of the greedy algorithm. Furthermore, no evolutionary algorithm exists in prior literature for MCSC that achieves such an approximation ratio in polynomial time. ## 1.1 Contributions This paper presents the novel algorithm, EASC (Evolutionary Algorithm for Submodular Cover, Alg. 1), which is the first polynomial-time evolutionary algorithm for MCSC with constant, bicriteria approximation ratio: EASC finds a solution A such that f(A) ≥ (1 - ϵ)τ and c(A) ≤ (ln(1/ϵ) + 1)c(A∗ ), where A∗ is an optimum solution and ϵ ∈ (0, 1) is an input parameter. The expected time is O(n3 ((cmax/cmin) ln(1/ϵ))2 ), where cmax and cmin are the maximum and minimum cost of a single element s ∈ S, respectively. If cmax/cmin is bounded by a polynomial in n and ϵ is a constant, then EASC finds a near-feasible solution to MCSC with a constant approximation ratio in expected polynomial time. In contrast to existing EAs that have been analyzed for submodular optimization problems [Qian et al., 2015b; 2015a; 2 The greedy algorithm is discussed in the Appendix in the full version of the paper. 3 Time is measured in number of evaluations of f and c, as is commonly done [Badanidiyuru and Vondr´ak, 2014]. 2017], EASC is not a generic EA for multi-objective optimization. Instead, EASC takes advantage of the structure of monotone submodular functions to quickly strengthen its population. A key idea in EASC is that the range [0, τ] is discretized into bins and subsets of X ⊆ S are mapped to bins based on the value of f(X). Solutions within a bin compete with one another using a novel measure of cost-effectiveness. Both the bin structure and notion of cost-effectiveness are designed to take advantage of monotonicity and submodularity. It is likely that these ideas have potential to be applied to monotone submodular optimization problems other than MCSC. EASC is experimentally evaluated on instances of the Influence Threshold Problem (IT) [Goyal et al., 2013; Kuhnle et al., 2017] on real social network datasets. EASC is compared to both the greedy algorithm as well as the existing EA that has been analyzed for MCSC, POM [Qian et al., 2015a]. Both EASC and POM are able to find better solutions than the greedy algorithm on the problem instances, which demonstrates the value of EAs for MCSC. In addition, EASC is shown to converge faster than POM on some instances. Organization. Related work is first discussed in Section 1.2. Then, EASC is described in detail in Section 2. Theoretical results on the approximation ratio of EASC are presented in Section 3. Finally, the application and an experimental analysis of EASC is given in Section 4. Notation. The following notation will be used throughout the paper. For x ∈ S, define c(x) = c({x}) and f(x) = f({x}). Define cmin = minx∈S c(x), and cmax = maxx∈S c(x). Let fτ(X) = min{f(X), τ} for all X ⊆ S. The notation for marginal gain is shortened to ∆f(X, x) = f(X ∪ {x}) - f(X) for X ⊆ S and x ∈ S. Finally, exp(a) denotes the exponential function a ↦→ ea . ## 1.2 RelatedWork Evolutionary algorithms (EAs) have previously been analyzed for submodular optimization problems [Friedrich and Neumann, 2015; Qian et al., 2015a; 2015b; 2017; Friedrich et al., 2018]. In general, these EAs work by maintaining a population of non-dominating 4 solutions. Iteratively, a random solution from the population is selected and mutated. If the new solution is not strictly dominated by an existing solution in the population, it is kept 5 in the population and solutions dominated by the new solution are removed from the population. These EAs are quite generic and apply broadly to multi-objective optimization problems. In contrast, EASC is designed specifically for MCSC. Friedrich and Neumann (2014) and Qian et al. (2015b) analyzed similar EAs for the problem of maximizing a monotone, submodular function with respect to a cardinality constraint k. Friedrich and Neumann obtained as good an approximation ratio as the greedy algorithm in expected O(n2 (log(n) + k)) time and Qian et al. in expected O(k2n) time for this problem. 4 A solution X is dominated by a solution Y if c(Y ) ≤ c(X) and f(Y ) ≥ f(X). The domination is strict if at least one of the inequalities is strict. 5 In addition, the EA may require that the new solution meet some requirement such as the cost being beneath a bound. ## Algorithm 1 Evolutionary Algorithm for MCSC (EASC) ``` Input: MCSC instance parameters f : 2S → R≥0, c : 2S → R≥0, and τ, bin parameters δ ∈ [1 - cmin/c(A∗ ), 1-cmin/c(S)] and ϵ ∈ (0, 1), and number of iterations T ∈ Z≥0. t = 1, B = {∅} bin ← The bin function induced by τ, δ, ϵ ≺← The comparison operator induced by τ, bin while t ≤ T do X uniformly randomly chosen from B X′ = mutate(X) if ∃Y ∈ B such that bin(Y ) = bin(X′ ) then if Y ≺X′ then B = B \ {Y } ∪ {X′ } end if elseB = B ∪ {X′ } end if t = t +1 end while ``` Qian et al. (2015a) analyzed an EA for MCSC called POM (Pareto Optimization Method) [Qian et al., 2015a]. Qian et al. proved that the population of POM would contain an Hcτ 6 = O(log(cτ)) approximate solution for MCSC in O(Nn(log(n) + log(cmax) + N))) expected time, where N is the number of distinct f values in [0, τ). In order that the approximation guarantees of POM be in expected polynomial time, the number of distinct values of f in the region of [0, τ) must be bounded by a polynomial. However, this is not a realistic assumption for many applications in machine learning and data mining, where f is real-valued and easily takes on exponentially many values in the region [0, τ) [Kuhnle et al., 2017; Mirzasoleiman et al., 2015]. The N in the number of expected time comes from the population size of POM. Hence in POM, the population can get quite large, which in turn affects the expected time before the approximation ratio is reached. A similar issue arises when an EA for the dual problem of MCSC is analyzed [Qian et al., 2017]. EASC does not have this problem as its population size is always O((cmax/cmin) ln(1/ϵ)n). There exist results on approximating a set of non-dominating solutions with a set of smaller size [Laumanns et al., 2002; Horoba and Neumann, 2009]. In fact, Laumanns et al. and Horoba and Neumann both describe approaches of binning solutions that serves a similar purpose to the bins in EASC, though the bins in EASC are quite different; among other reasons, solutions that dominate others in the population of EASC are possible. However, it is not clear that the approaches described by Laumanns et al. and Horoba and Neumann could be done efficiently in this context nor could result in approximation ratios in expected polynomial time. 6 c is the minimum real number making cf(X) for all X ⊆ S and cτ integers, and the cτ harmonic number is Hcτ = ∑cτ j=1 1/j. ## 2 Evolutionary Algorithm for MCSC (EASC) In this section, the algorithm EASC (Evolutionary Algorithm for Submodular Cover) is introduced. Pseudocode for EASC can be found in Algorithm 1. EASC is designed for finding good approximate solutions to instances of MCSC efficiently. As will be shown in Section 3, if the input parameter ϵ is constant and cmax/cmin is bounded by a polynomial, then EASC provides a near-feasible solution to MCSC with a constant approximation ratio in expected polynomial time. Fundamental to EASC is a mapping from 2S to O((cmax/cmin) ln(1/ϵ)n) bins; bin j is associated with the subinterval and a subset X ⊆ S is mapped into the bin where min{f(X), τ} falls. The population B ⊆ 2S , which is a set of subsets of S, contains at most one subset of S per bin. The bins are discussed in more detail in Section 2.1. The input parameters ϵ ∈ (0, 1) and δ ∈ [1 - cmin/c(A∗ ), 1 - cmin/c(S)], where A∗ is an optimal solution to the instance, determine the number of bins and the intervals for each bin. Lower ϵ and δ values result in less bins, and hence a smaller population size. To find a δ in the required range, δ can be set to 1 - cmin/B where B is an upper bound on c(A∗ ) such that B ≤ c(S). In the experiments in Section 4, B is set to the cost of the greedy solution. The number of iterations of EASC is determined by the input parameter T . At each iteration, EASC chooses a solution X ∈ B to mutate to X′ , under the mutation process described in Section 2.3. If it is not the case that X′ is mapped to a bin with a better solution according to comparison ≺, X′ is added to B, and the weaker solution is removed, if any. The comparison operator ≺ is discussed in Section 2.2. The structure of the bins and the comparison operator ≺ are motivated by monotonicity and submodularity, as described in Sections 2.1 and 2.2. ## 2.1 The Bin Function In EASC, [0, τ ] is discretized into logδ(ϵ) + 1 intervals associated with bins. Every X ⊆ S is mapped to the bin where min{f(X), τ} falls: The function bin takes X ⊆ S and returns a bin number in {0, ..., logδ(ϵ)} as follows: The bins are depicted in Figure 1. The population B in EASC contains at most one solution for each bin, and therefore is bounded in size by logδ(ϵ) + 1. A solution X ∈ B that maps to bin logδ(ϵ) (the final bin) is near-feasible: f(X) ≥ (1-ϵ)τ. It is the solution mapped to this bin that will give the approximation ratio in expected polynomial time. Using the fact that δ ≤ 1 - cmin/c(S), the total number of bins is bounded as follows. Proposition 1. The number of bins is at most Figure 2: An illustration of the cost-effectiveness φ for X where bin(X) ∈ {1, ..., logδ (ϵ) - 1}. On both the c(X) and f(X) axis, left is greater. Lower values of φ(X) means more cost-effective. ![Image](https://ijcai.org/proceedings/2019/fulltext/171/image_000000_ea46dbae3adfac4891e83dcbb81f29bf03c42261d302b66857e1a93f80c2204a.png) Proof. It is the case that The motivation behind the interval assignment of each bin comes from the greedy algorithm for MCSC. Suppose the sequence of elements a1, ..., ak is chosen by the greedy algorithm for the instance of MCSC. Let Ai = {a1, ..., ai}. It is the case 7 that for i < k the marginal gain at each step is lower bounded as follows: where A∗ is an optimal solution to the instance of MCSC. If δ ≥ 1 - cmin/c(A∗ ) the region of each bin mimics this marginal gain. Intuitively, the bins can be thought of like steps in the greedy algorithm. EASC holds on to the best solution for each step. ## 2.2 Comparison Operator ≺ If two solutions in B map to the same bin, then the weaker solution is removed. Weaker is determined by the comparison operator ≺. ≺ uses a novel measure of cost-effectiveness, φ, in order to compare solutions. Let X ⊆ S. If bin(X) = 0 or bin(X) = logδ(ϵ), then φ(X) = c(X). Otherwise Notice that lower φ means better cost-effectiveness. Then Y ≺ X if and only if bin(X) = bin(Y ) and φ(X) < φ(Y ). Figure 2 illustrates the cost-effectiveness φ(X) for varying values of c(X) and f(X) for bin(X) ∈ {1, ..., logδ(ϵ) - 1}. Lower values of c(X) and higher values of f(X) result in lower φ(X) (which means more cost-effective). But as f(X) decreases, differences in c(X) are amplified in φ(X). Therefore, c matters more when comparing solutions in lower bins, and in higher bins (excluding the last) f matters more. This encourages solutions in B to rise up (via mutation) to the final bin, where a (1 - ϵ)-feasible solution is held. 7 See the Appendix in the full version of the paper. Figure 1: The region [0, τ ] is discretized into logδ (ϵ) + 1 bins in EASC. Solutions X ⊆ S are mapped into the bin corresponding to the region where min{f(X), τ} falls. B contains at most 1 subset of S for each bin. ![Image](https://ijcai.org/proceedings/2019/fulltext/171/image_000001_43596d261f8d6407c3bfeb3013dc57496c35c90515115a86f2a5727891a396d0.png) Like the bins discussed in Section 2.1, the motivation for ≺ is the greedy algorithm for MCSC. Again, consider the sequence of elements chosen by the greedy algorithm a1, ..., ak and let Ai = {a1, ..., ai}. For i < k it is the case 8 that Therefore at every iteration the greedy algorithm has a solution Ai where φ(Ai) ≤ c(A∗ ). In a sense, a solution X ⊆ S such that φ(X) ≤ c(A∗ ) has as good of cost-effectiveness as solutions picked by the greedy algorithm. ≺ ensures that if B contains a solution X such that φ(X) ≤ c(A∗ ), then X cannot be replaced with a solution that is less good in that sense. ## 2.3 Mutation of Elements in B Random mutation of solutions in the population occur in the same fashion as existing Pareto optimization algorithms [Qian et al., 2015b]. At each iteration of EASC, an element X ∈ B is chosen uniformly randomly to be mutated. X is mutated into X′ as follows: Every x ∈ X is removed from X with independent probability 1/n. Every x /∈ X is added to X with independent probability 1/n. The number of elements expected to change fromX to X′ is 1. X′ is added to B if there does not exist a Y ∈ B mapping to the same bin as X′ such that X′ ≺ Y . If no such Y exists, then X′ is added to B and any existing solution in the bin of X′ is removed. ## 3 Approximation Results In this section, the number of iterations before EASC contains a near-feasible solution for MCSC with an approximation ratio of ln(1/ϵ)+1 is analyzed, where ϵ ∈ (0, 1) is an input parameter of EASC. Each iteration of EASC involves exactly one evaluation each of f and c. If time is measured in evaluations of f and c, as is commonly done [Badanidiyuru and Vondr´ak, 2014], then the expected time is a constant times the expected number of iterations. The approximation guarantee in Theorem 1 is a bicriteria approximation guarantee, which means that both the feasibility constraint 9 and the minimum cost are approximated. Algorithms with bicriteria approximation guarantees have previously been considered for submodular optimization problems [Iyer and Bilmes, 2013]. If ϵ is assumed to be a constant and cmax/cmin bounded by a polynomial in n, then Theorem 1 shows that EASC finds a near-feasible solution with a constant approximation ratio in expected polynomial iterations. 8 See the Appendix in the full version of the paper. 9 The set X is feasible iff f(X) ≥ τ . Theorem 1. Suppose that we have an instance of MCSC with optimal solution A∗ ̸= ∅, and EASC is run indefinitely with input ϵ ∈ (0, 1) and δ ∈ [1 - cmin/c(A∗ ), 1 - cmin/c(S)]. Then B contains a set A in bin logδ(ϵ) such that f(A) ≥ (1- ϵ)τ and where A∗ is an optimum solution, in expected number of iterations at most Once a solution that fits the criteria of Theorem 1 appears in bin logδ(ϵ), it cannot be replaced by one that does not since the comparison operator ≺ compares based on only c in the last bin. Notice that Theorem 1 does not contradict the optimality of the ln(n)-approximation ratio for the set cover problem [Feige, 1998], since the guarantee is bicriteria. The same bicriteria approximation guarantee in Theorem 1 holds for the greedy algorithm 10 . The proof of Theorem 1 tracks cost-effective solutions in B over the duration of EASC. A set X is cost-effective if it satisfies one of the following (mutually exclusive) conditions: Once a cost-effective set is in the final bin, a solution that meets the criteria of Theorem 1 is in the population. By design, EASC never replaces a cost-effective solution in its population with one that is not cost-effective. In addition, because of the requirement that δ ≥ 1 - cmin/c(A∗ ), the bins are structured tightly enough so that there is a significant probability that cost-effective solutions mutate into cost-effective solutions in strictly greater bins. Together, these points enable EASC to contain a cost-effective solution in its final bin in polynomial expected iterations. The following lemmas will be used to prove Theorem 1. The lemmas are not novel to this work, but have previously been used to analyze the approximation guarantee of the greedy algorithm for MCSC [Goyal et al., 2013]. Proofs of the lemmas are included in the Appendix in the full version of the paper. Lemma 1. Suppose that we have an instance of MCSC with optimal solution A∗ ̸= ∅. Let X ⊆ S and x∗ = argmaxx∈S ∆fτ (X, x)/c(x). Then 10 This result was originally proven for an influence application by Goyal et al. (2013) but holds for general MCSC. See the Appendix in the full version of the paper for the proof. Lemma 2. Suppose that we have an instance of MCSC with optimal solution A∗ ̸= ∅. Let X ⊆ S such that f(X) < τ and x∗ = argmaxx∈S ∆fτ (X, x)/c(x). Then c(x∗ ) ≤ c(A∗ ). Proof of Theorem 1. Recall that notation is defined in Section 1. For brevity, let r = logδ(ϵ) be the final bin. There always exists at least one cost-effective solution in B: The empty set is cost-effective since φ(∅) = c(∅) = 0 < c(A∗ ), and the empty set is never removed from B because there does not exist Y ⊆ S such that c(Y ) < 0 = c(∅). Note that this means if a solution is removed from B, it can be assumed that it did not correspond to bin 0. Define an infinite sequence ℓt, t ∈ {1, 2, ...}, where ℓt is the max value in {0, ..., r} such that there exists a cost-effective solution X ∈ B where bin(X) = ℓt at the beginning of iteration t of EASC. Part One. First, it is shown that the sequence ℓt is nondecreasing. Let X be the cost-effective set corresponding to ℓt at the beginning of iteration t. If X is not removed from B during the tth iteration, then clearly ℓt ≤ ℓt+1. Suppose X is removed from B during the tth iteration. Then X was replaced with X′ such that X ≺ X′ and bin(X) = bin(X′ ). Let b = bin(X) = bin(X′ ). As explained above, b ̸= 0. Suppose b = r. Then X ≺ X′ implies that c(X′ ) < c(X) ≤ (ln(1/ϵ) + 1) c(A∗ ). Therefore X′ is costeffective. If b ∈ {1, ..., r - 1}. Then X ≺ X′ implies that φ(X′ ) < φ(X) ≤ c(A∗ ) and hence X′ is also cost-effective. In both of these cases, ℓt = ℓt+1. Part Two. Second, it is shown that if bin(X) < r and then bin(X ∪ {x∗ }) > bin(X). Let a = bin(X). Lemma 1 and that δ ≥ 1 - cmin/c(A∗ ) implies By definition of the bins fτ (X) ≥ (1 - δa )τ , and therefore Since a < r, it is the case that bin(X ∪ {x∗ }) ≥ a + 1. Part Three. Third, it is shown that if X is cost-effective, bin(X) < r, and x∗ defined as in Part Two, then X ∪ {x∗ } is cost-effective. Let a = bin(X) and b = bin(X ∪ {x∗ }). To show the cost-effectiveness of X ∪ {x∗ }, four cases are analyzed based on the values of a and b. Case (i): b < r and a = 0. In this case, X = ∅ as explained at the beginning of the proof, and X ∪ {x∗ } = {x∗ }. Lemma 1 states that which can be re-arranged to see that φ(x∗ ) ≤ c(A∗ ) and hence X ∪ {x∗ } is cost-effective. Case (ii): b < r and a > 0. Since b, a < r it is the case that fτ (X ∪ {x∗ }) = f(X ∪ {x∗ }) and fτ (X) = f(X). Lemma 1 gives that Using the upper bound on τ - f(X) given by re-arranging φ(X) ≤ c(A∗ ) implies that which may be re-arranged to see that X ∪ {x∗ } is costeffective. Case (iii): b = r and a > 0. X being cost-effective and a < r imply that c(X ∪ {x∗ }) = By Lemma 2, c(x∗ ) ≤ c(A∗ ). Therefore X ∪ {x∗ } is costeffective. Case (iv): b = r and a = 0. Then X = ∅ as explained at the beginning of the proof. Then c(X ∪ {x∗ }) = c(x∗ ) ≤ c(A∗ ) by Lemma 2, and therefore X ∪ {x∗ } is cost-effective. Part Four. It is now shown that if at iteration t, the costeffective set X associated with ℓt < r is mutated into X ∪ {x∗ }, then ℓt < ℓt+1. Suppose X is mutated into X ∪ {x∗ } on iteration t. X ∪ {x∗ } is cost-effective by Part Three. Let b = bin(X ∪ {x∗ }). By Part Two, b > ℓt. If there does not exist Y ∈ B at the beginning of iteration t such that bin(Y ) = b, then X ∪{x∗ } is added to B. Then ℓt+1 = b. Suppose there does exist a Y ∈ B at the beginning of iteration t such that bin(Y ) = b. Y is not cost-effective by definition of ℓt. Then if b = r, and so Y ≺ X ∪ {x∗ }. Then Y is replaced with X ∪ {x∗ } in B. If b < r, and recalling that b ̸= 0 as explained at the beginning of the proof, then Therefore again Y ≺ X ∪ {x∗ }, so Y is replaced with X ∪ {x∗ } in B. In both cases, ℓt+1 = b. Part Five. Finally, the expected number of iterations until ℓt = r is analyzed. Once ℓt = r, the solution in B mapping to bin r satisfies the conditions of the theorem statement. Suppose it is the beginning of iteration t of EASC such that ℓt < r. Then with probability at least the set X corresponding to ℓt will be chosen and mutated into X∪{x∗ }. By Part Four, if this occurs ℓt < ℓt+1. By Part One, the sequence is non-decreasing. This means that the expected number of steps for ℓt to reach r is at most enr(r + 1). The bound on r given by Proposition 1 of Section 2.1 gives the theorem statement. ## 4 Experimental Analysis In this section, EASC is experimentally evaluated on instances of the Influence Threshold Problem (IT) [Goyal et al., 2013], a special case of MCSC. EASC is compared to the greedy algorithm and POM [Qian et al., 2015a]. In all experiments, EASC and POM find solutions of lower cost than the greedy algorithm, and in most cases EASC converges faster than POM to a low cost. Code to run the experiments is publicly available at https://gitlab.com/vcrawford/easc.git. Figure 3: Over the duration of EASC and POM, the minimum cost of any solution in the population with f value above (1 - ϵ)τ is plotted. Both cost and number of f evaluations are normalized by that of the greedy algorithm. ![Image](https://ijcai.org/proceedings/2019/fulltext/171/image_000002_3639b0a1ea88dbbe1a4143d80c83d4ba6b87fba1cafa3adeafb4472dea987fa8.png) ## 4.1 Application and Setup The experiments are run on instances of the Influence Threshold Problem, defined as follows. Let G = (V, E) be a social network where vertices V represents users, and directed edges E represent social connections. Activation of users in the social network starts from an initial seed set and then propagates across "live edges" according to the independent cascade model [Kempe et al., 2003], in which every edge (u, v) ∈ E has an independent probability puv of being live. For every user v ∈ V , there is a cost cv of seeding that user. The cost of seeding a set X is c(X) = ∑x∈X cx. The function f(X) is the expected number of users that will become active if X is seeded; f is monotone submodular [Kempe et al., 2003]. Then the IT problem is defined as follows: given an activation threshold τ , find argmin{c(X) : X ⊆ S, f(X) ≥ τ }. The experiments are run on four real social networks from SNAP [Leskovec and Krevl, 2015]: ca-GrQc (n = 5242), ca-HepPh (n = 12008), wiki-Vote (n = 7115), and egoFacebook (n = 4039). The independent cascade model is used to model activation from a seed set for the above four social networks with constant edge probabilities p = 0.07, p = 0.02, p = 0.04, and p = 0.013, respectively. Computing the expected activation f(X) under the independent cascade model is #P-hard [Chen et al., 2010]. Instead of evaluating f directly, the reverse influence sampling approach [Borgs et al., 2014] with 100,000 samples is used in order to approximate f. The same set of samples is used for all algorithms on a data set. The cost function c(X) = ∑x∈X cx, where every node v in the social network is assigned a cost cv that is its outgoing degree perturbed by random multiplicative noise 11 In particular, node v with outdoing degree d has cost 1 + (1 + |ξ|)d where ξ ∼ N (µ = 0, σ = 0.5)12 . 11 Under this model of cost, social network users with more outgoing edges are generally more expensive to seed, but individual preferences factor into the price of seeding via random noise. 12 A normal distribution with mean 0 and standard deviation 0.5. The instance of MCSC for each social network is run with a different threshold τ. The greedy algorithm is run with input τ and ϵ = 0.05. EASC is run with τ, ϵ = 0.05, and δ = 1 - cmin/B where B is the cost of the output of the greedy algorithm when run with τ and ϵ = 0. POM is run with threshold (1 - ϵ)τ for fair comparison with EASC, although POM is not a bicriteria algorithm. EASC and POM are run 3 times on each instance, and the results are averaged. ## 4.2 Results The experimental results are plotted in Figure 3. At small intervals over the duration of EASC and POM, the minimum cost of any solution in the population with f value above (1 - ϵ)τ is plotted. The cost and the number of f evaluations are normalized by that of the greedy algorithm. That is, if the greedy algorithm returned a set G, then the costs plotted are normalized by c(G) and the number of function evaluations are normalized by n|G|. In all experiments, EASC and POM were able to find a better solution than the greedy algorithm. In ca-HepPh (Figure 3(b)), both EASC and POM find a better solution than the greedy algorithm in less f evaluations. These results demonstrate an ability to improve on the solution quality of the greedy algorithm. In ca-GrQc (Figure 3(a)) and wiki-Vote (Figure 3(c)), EASC finds a better solution more quickly than POM throughout the entire experiment. In contrast, in ca-HepPh (Figure 3(b)) and ego-Facebook (Figure 3(d)) POM finds a better solution more quickly in the earlier stages of the experiment, but EASC catches up and either outperforms POM for the remainder of the iterations (caHepPh) or converges to about the same performance. This behavior may be explained by the fact that at first POM has a smaller population since every solution competes with every other solution, unlike EASC where competition is restricted to within bins. But as the population of POM gets larger (at least 3 times larger than EASC at the end of these experiments), the improvement of POM is slowed. ## Acknowledgements Victoria G. Crawford was supported by a Harris Corporation Fellowship. Alan Kuhnle provided helpful feedback in preparation of the manuscript. ## References 1. [Badanidiyuru and Vondrák, 2014] Ashwinkumar Badani- diyuru and Jan Vondrák. Fast algorithms for maximizing submodular functions. In Proceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithms, pages 1497-1514. SIAM, 2014. 2. [Borgs et al., 2014] Christian Borgs, Michael Brautbar, Jen- nifer Chayes, and Brendan Lucier. Maximizing social influ- ence in nearly optimal time. In Proceedings of the twenty- fifth annual ACM-SIAM symposium on Discrete algorithms, pages 946-957. SIAM, 2014. 3. [Chen et al., 2010] Wei Chen, Chi Wang, and Yajun Wang. Scalable influence maximization for prevalent viral mar- keting in large-scale social networks. In Proceedings of the 16th ACM SIGKDD international conference on Knowl- edge discovery and data mining, pages 1029-1038. ACM, 2010. 4. [Feige, 1998] Uriel Feige. A threshold of ln n for approximat- ing set cover. Journal of the ACM (JACM), 45(4):634-652, 1998. 5. [Friedrich and Neumann, 2014] Tobias Friedrich and Frank Neumann. Maximizing submodular functions under ma- troid constraints by multi-objective evolutionary algorithms. In International Conference on Parallel Problem Solving from Nature, pages 922-931. Springer, 2014. 6. [Friedrich and Neumann, 2015] Tobias Friedrich and Frank Neumann. Maximizing submodular functions under ma- troid constraints by evolutionary algorithms. Evolutionary computation, 23(4):543-558, 2015. 7. [Friedrich et al., 2018] Tobias Friedrich, Andreas Göbel, Francesco Quinzan, and Markus Wagner. Heavy-tailed mutation operators in single-objective combinatorial opti- mization. In International Conference on Parallel Problem Solving from Nature, pages 134-145. Springer, 2018. 8. [Goyal et al., 2013] Amit Goyal, Francesco Bonchi, Laks VS Lakshmanan, and Suresh Venkatasubramanian. On mini- mizing budget and time in influence propagation over social networks. Social network analysis and mining, 3(2):179- 192, 2013. 9. [Guillory and Bilmes, 2011] Andrew Guillory and Jeff A Bilmes. Simultaneous learning and covering with adversar- ial noise. In ICML, volume 11, pages 369-376, 2011. 10. [Horoba and Neumann, 2009] Christian Horoba and Frank Neumann. Additive approximations of pareto-optimal sets by evolutionary multi-objective algorithms. In Proceedings of the tenth ACM SIGEVO workshop on Foundations of genetic algorithms, pages 79-86. ACM, 2009. 11. [Iyer and Bilmes, 2013] Rishabh K Iyer and Jeff A Bilmes. Submodular optimization with submodular cover and sub- modular knapsack constraints. In Advances in Neural In- formation Processing Systems, pages 2436-2444, 2013. 12. [Kempe et al., 2003] David Kempe, Jon Kleinberg, and Éva Tardos. Maximizing the spread of influence through a social network. In Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, pages 137-146. ACM, 2003. 13. [Kuhnle et al., 2017] Alan Kuhnle, Tianyi Pan, Md Abdul Alim, and My T Thai. Scalable bicriteria algorithms for the threshold activation problem in online social networks. In INFOCOM 2017-IEEE Conference on Computer Commu- nications, IEEE, pages 1-9. IEEE, 2017. 14. [Laumanns et al., 2002] Marco Laumanns, Lothar Thiele, Kalyanmoy Deb, and Eckart Zitzler. Combining conver- gence and diversity in evolutionary multiobjective optimiza- tion. Evolutionary computation, 10(3):263-282, 2002. 15. [Leskovec and Krevl, 2015] Jure Leskovec and Andrej Krevl. {SNAP Datasets}:{Stanford} large network dataset collec- tion. 2015. 16. [Mirzasoleiman et al., 2015] Baharan Mirzasoleiman, Amin Karbasi, Ashwinkumar Badanidiyuru, and Andreas Krause. Distributed submodular cover: Succinctly summarizing massive data. In Advances in Neural Information Process- ing Systems, pages 2881-2889, 2015. 17. [Mirzasoleiman et al., 2016] Baharan Mirzasoleiman, Morteza Zadimoghaddam, and Amin Karbasi. Fast distributed submodular cover: Public-private data summa- rization. In Advances in Neural Information Processing Systems, pages 3594-3602, 2016. 18. [Norouzi-Fard et al., 2016] Ashkan Norouzi-Fard, Abbas Bazzi, Ilija Bogunovic, Marwa El Halabi, Ya-Ping Hsieh, and Volkan Cevher. An efficient streaming algorithm for the submodular cover problem. In Advances in Neural Information Processing Systems, pages 4493-4501, 2016. 19. [Qian et al., 2015a] Chao Qian, Yang Yu, and Zhi-Hua Zhou. On constrained boolean pareto optimization. In IJCAI, pages 389-395, 2015. 20. [Qian et al., 2015b] Chao Qian, Yang Yu, and Zhi-Hua Zhou. Subset selection by pareto optimization. In Advances in Neural Information Processing Systems, pages 1774-1782, 2015. 21. [Qian et al., 2017] Chao Qian, Jing-Cheng Shi, Yang Yu, and Ke Tang. On subset selection with general cost constraints. In Proceedings of the 26th International Joint Conference on Artificial Intelligence (IJCAI-2017), pages 2613-2619, 2017. 22. [Wolsey, 1982] Laurence A Wolsey. An analysis of the greedy algorithm for the submodular set covering problem. Com- binatorica, 2(4):385-393, 1982.