{'fraction_non_alphanumeric': 0.055186087818579865, 'fraction_numerical': 0.01705977115948614, 'mean_word_length': 4.081863979848866, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 1, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 9, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Efficient Algorithms for Monotone Non-Submodular Maximization with Partition Matroid Constraint

In this work, we study the problem of monotone non-submodular maximization with partition matroid constraint. Although a generalization of this problem has been studied in literature, our work focuses on leveraging properties of partition matroid constraint to (1) propose algorithms with theoretical bound and efficient query complexity; and (2) provide better analysis on theoretical performance guarantee of some existing techniques. We further investigate those algorithms' performance in two applications: Boosting Influence Spread and Video Summarization. Experiments show our algorithms return comparative results to the state-of-the-art algorithms while taking much fewer queries.


Introduction
Maximizing classes of set functions, generalizing submodular functions, has emerged recently due to its wide range applications in real-world problems. Among those works, nonsubmodular maximization subject to cardinality constraint was studied the most extensively, including but not limited to [Bian et al., 2017;Das and Kempe, 2011;Qian et al., 2018;Kuhnle et al., 2018].
However, cardinality constraint may not be sufficient to capture some natural requirements of various applications. For example, in many viral marketing campaigns, it is important to ensure the diversity and fairness among different ethnics and genders. These applications aim to distribute budget to feed information fairly among different groups of users while guaranteeing to maximize the influence spread in the network. Another example is data summarization. In many situations, a large data may be formed by elements of various classes. The problem, thus, aims to find a representative subset to cover the dataset's content as much as possible while imposing a constraint that the subset should contain a number of members of each class to guarantee diversity.
Motivated by those observation, we study the following problem: Given a ground set V , a non-negative monotone function f : 2 V → R ≥ ; let V 1 , ..., V k be a collection of disjoint subsets forming V (i.e. V = V 1 ... V k ), and b 1 , ..., b k be k integers that 1 ≤ b i ≤ |V i | ∀i ∈ [k]. The problem asks for: MAXMP is formally represented as monotone nonsubmodular maximization with partition matroid constraint. This constraint is a special case of matroid constraint and generalizes cardinality constraint. Non-submodular maximization beyond cardinality constraint was only received attention recently. The most recent works are [Chen et al., 2018] and [Gatmiry and Gomez-Rodriguez, 2018], in which they studied the performance guarantee of GREEDY or RESID-UAL GREEDY (RESGREEDY) [Buchbinder et al., 2014] on monotone non-submodular maximization subject to matroid constraint. However, those algorithms requires O(nK) queries of f (K is a rank of a matroid), which may not be desirable in practice. Researchers [Mirzasoleiman et al., 2016;Badanidiyuru and Vondrák, 2014;Kuhnle et al., 2018] have sought ways to speed up the GREEDY algorithm. Unfortunately, these approaches were only for cardinality constraint; or relied upon the submodularity of f .
To our knowledge, there exists no specific work dedicating for non-submodular maximization subject to partition matroid constraint. That leaves us open questions on: (1) With partition matroid, does there exist an algorithm with a better ratio or can we improve the ratio of the existing algorithms, whose performance guarantees have been proven with a matroid constraint? (As partition matroid is a special case of matroid constraint, perhaps we can get a tighter ratio if we only considered the partition matroid.) (2) Can we leverage partition matroid properties to devise approximation algorithms with more query-efficient?
Our Contribution. In this work, we focus on answering those two above questions. First, to quantify the nonsubmodularity of a function, we introduce Partition Matroid Curvature α and Partition Matroid Diminishing-Return ratio γ. These two quantities are derived from a same concept with the diminishing-return ratio [Lehmann et al., 2006;Bogunovic et al., 2017] and generalized curvature [Bian et al., 2017;Conforti and Cornuéjols, 1984;Iyer et al., 2013] but have more relaxed requirement.
Our main contribution is to introduce a novel approximation algorithm, named PROB, with approximation ratio of (1/γ ′ − 1 + α ′ )(1 − 1/Θ(max i∈[k] |V i |)) + 1 where γ ′ and α ′ are non-trivial and obtainable bounds of γ and α. PROB's novelty lies in a random process of selecting a new element, in which the algorithm introduces a new probability distribution among non-selected elements. That probability distribution is a key for PROB to obtain its ratio. Furthermore, by utilizing a sampling technique to reduce searching space, we propose FASTPROB, an algorithm improving from PROB with efficient query complexity of O(n ln 2 i∈[k] b i ). Moreover, we re-investigate theoretical performance of two existing techniques, GREEDY and THRESHOLD GREEDY (THRGREEDY). We proved that: with partition matroid constraint, GREEDY can obtain a ratio of min α/(1 − (1 − αγ/ i∈[k] b i ) min i∈[k] bi ), (1 + γα)/γ , which -in comparing with existing work of [Friedrich et al., 2019] in matroid constraint -has its own advantage in some certain range of non-submodular quantification parameters.
Finally, we investigate our algorithms' performance on two applications of MAXMP: Boosting Influence Spread and Video Summarization. We provide bounds on the objective functions' partition matroid curvature and diminishing ratio to have a better insight on theoretical guarantees of our algorithms. Experimental results show our algorithms return comparable solutions to the state-of-the-art techniques while totally outperform them in the number of queries.

Related Work
Quantifying non-submodularity. To bound how close a function to submodularity, three most popular quantities in literature are: (1) weakly submodular ratio; (2) diminishing return ratio; and (3) generalized curvature. Weakly submodular ratio, denoted as γ s , was first introduced by [Das and Kempe, 2011] and further used by [Elenberg et al., 2017;Qian et al., 2015;Chen et al., 2018]. γ s is defined as the maximum value in range Bogunovic et al., 2018;Lehmann et al., 2006;Qian et al., 2018;Kuhnle et al., 2018] is defined as the largest value in range γ d was proven to be at most the value of γ s [Kuhnle et al., 2018].
General curvature α c [Bian et al., 2017;Conforti and Cornuéjols, 1984;Iyer et al., 2013], on another hand, is the smallest number in In this work, we adapt DR-ratio and curvature but with more relaxed requirements. To be specific, instead of requiring those quantities applicable for all sets, we narrow down the collection of subsets S ⊆ T that need to satisfy those properties to |(T \ S) ∩ V i | ≤ b i for all i ∈ [k]. If considering size constraint, this relaxation is corresponding to the definition of Greedy DR-ratio and Greedy Curvature [Bian et al., 2017;Kuhnle et al., 2018]. Not only this relaxation is sufficient to bound our approximation ratios; but also it helps us obtaining meaningful bounds of those quantities in the MAXMP's applications of our experiments.
Beyond Cardinality Constraint. Non-submodular max-imization beyond cardinality constraint has received attention recently. [Chen et al., 2018] was the first one brought up the concept of non-submodular maximization subject to matroid constraint. In this work, the author proved that RESGREEDY can obtain the ratio of (1 + 1 γs ) 2 . [Gatmiry and Gomez-Rodriguez, 2018] then proved GREEDY is able to obtain a ratio of √ γsK+1 0.4γ 2 s and 1 + 1/γ d . In submodular maximization, the study beyond cardinality constraint is too extensive to give a comprehensive overview. Due to space limit, we only go over representative works; and refer readers to comprehensive discussion on [Calinescu et al., 2011;Buchbinder et al., 2019;Friedrich et al., 2019].
For Cornnejols et al., 1977] -has been considered as the best algorithm for monotone submodular maximization subject to matroid constraint. This was up until [Calinescu et al., 2011] introduced a concept of multilinear extension of submodular functions to devise a 1/(1 − 1/e) algorithm. However, their expensive complexity remains a significant bottleneck to make the algorithm applicable; and how to reduce or improve it is still an intriguing open question for future research. The newest breakthrough is of [Buchbinder et al., 2019], who devised an algorithm, namely SPLITGROW, with a ratio of 1/0.5008 andÕ(nK 2 + KT ) complexity -where T is the complexity to find a maximum weight perfect matching in a bipartite graph with 2K vertices.
The most recent work on partition matroid, to our knowledge, is of [Friedrich et al., 2019], in which the authors proved GREEDY is able to obtain a ratio of We generalizes this work to non-submodular objective function by providing analysis that GREEDY can obtain a ratio of min α/(1 − (1 − αγ/ i∈[k] b i ) min i∈[k] bi ), 1/γ + α . If only considering submodular objective function, our ratio has an advantage that it is bounded by 1/γ + α. Therefore, its ratio does not degrade when the input is formed by many partitions.
We also provide approximation ratio of THRGREEDY. THRGREEDY has been studied by [Kuhnle et al., 2018] in the problem of monotone non-submodular maximization with cardinality constraint. Since partition matroid generalizes cardinality constraint, our analysis techniques are totally different to [Kuhnle et al., 2018]. If projecting our ratio to cardinality constraint, our ratio is better than the one of [Kuhnle et al., 2018], which is 1/(1 − e −γ d γs(1−ǫ) − ǫ). The keys help us obtain a better ratio are (1) γ s is not necessary to bound inequality between obtained solutions and the optimal solution; and (2) we utilizes the general curvature to tighten the inequality equations, thus our ratio becomes better if the curvature moves away from the trivial value 1.

Definitions and Notations
Given a set function f , a set S and e ∈ S, denote ∆ e f (S) := f (S ∪ {e}) − f (S).
Given the partition matroid constraint of MAXMP, includ-

Definition 1. Given an instance of MAXMP, including
It is unknown in the literature on how hard it is to obtain exact values of quantities quantifying non-submodularity. γ and α are not exception either. Fortunately, for some applications, we can obtain non-trivial bounds of γ and α, which can help assess approximation ratios of our algorithms. We denote γ ′ as a lower bound of γ, e.g. γ ≥ γ ′ ≥ 0; and α ′ as a upper bound of α, e.g. α ≤ α ′ ≤ 1.
W.l.o.g, we assume the objective function f is normalized, i.e. f (∅) = 0, and b i ≤ n i for all i ∈ [k]. In our algorithms' analysis, we denote S * as an optimal solution, i.e f (S * ) = max S:|S∩Vi|≤bi f (S).

PROB and FASTPROB Algorithms
In this section, we describe PROB, a randomized algorithm with approximation ratio of (1/γ ′ − 1 + α ′ ) 1 − 1/O(n) + 1. Pseudocode of PROB is presented by Alg. 1. In general, PROB works in rounds, and at each round, one member of The key for PROB to obtain efficient performance guarantee lies in a random process, which introduces a probability distribution, defined locally for each group, to select a new element of each group to add into the obtained solution (line 6 Alg. 1). This random process allows us to construct a sequence of maximal sets in order to form a recursive relationship among changes on the f 's values of the obtained solutions, which is critical to bound PROB's approximation ratio.
and S 1 , ..., S b as a sequence of obtained solution by PROB. We prove the approximation ratio of PROB by constructing a sequence of maximal sets S * 0 , ..., S * b that satisfies the following properties: To construct the sequence, starting with S * 0 = S * , for each t = 1, ..., b − 1, S * t+1 is formed from S * t , S t and e t as follows: Let i be the index being considered at the for loop (line 3 Alg. 1); and e t will be added into S t .
probability e is selected). We have: where Equ. (4) is from properties of γ and α; while Equ. (7) is from AM-GM inequality.
How PROB's theoretical performance compares to existing algorithms?
Due to differences in definition of the quantities quantifying non-submodularity and how algorithms' ratios depend on them, it is no straight way to compare their ratios. For example, RESGREEDY obtains (1 + 1 γs ) 2 -ratio [Chen et al., 2018]. Although γ s ≥ γ ≥ γ ′ , it is unclear how this ratio is compared with PROB's ratio. However, PROB has a better query complexity than RESGREEDY (O(nb)).
When f is submodular (γ = 1), PROB can obtain a ratio of 1 + α ′ (1 − 1 n+2 ). Although PROB's ratio is still not comparable to the best ratio (1 − 1/e) of [Calinescu et al., 2011], their expensive complexity O(n 8 ) remains a significant bottleneck to make their algorithm applicable in practice. In compare with the most recent work [Buchbinder et al., 2019], PROB can reach a better ratio than SPLITGROW ( 1 0.5008 ) with appropriate values of α ′ andn; and PROB has much better query complexity than SPLITGROW (O(nb 2 )).

Improve PROB's complexity
PROB's query complexity can be improved by observing that the proof of Theorem 2 can non-trivially go through if e t is selected from a set that overlaps with (S * t \ S t ) ∩ V i for all t = 1, ..., b. This always works in Alg. 1 since e t is selected from V i \ S t . Therefore, we can use sampling to reduce the space of selecting e t as in Alg. 2.
We call Alg. 2 FASTPROB. The condition, which helps FASTPROB has the same ratio as PROB with probability at least 1 − δ, is guaranteed as stated in the following lemma.
for each i ∈ I do 4: which completes the proof.
Theorem 2. FASTPROB obtains a 1 γ ′ +α ′ −1 1− 1 n+2 + 1-approximation solution with probability at least 1 − δ and has query complexity of O(n ln b ln b δ ). Proof. Majority proof of FASTPROB's approximation ratio overlaps with the proof of PROB. Due to space limit and for the sake of completeness, we provide the proof of FAST-PROB's ratio in Appendix A.
In term of query complexity, it is trivial that the number of queries of FASTPROB is where Equ. (16) is from the fact that log x is a concave function, so i α i log x i ≤ log α i x i if i α i = 1; and Algorithm 3 GREEDY

GREEDY-like Algorithms
We re-study the theoretical performance guarantee of two algorithms, GREEDY and THRGREEDY. Our analysis provides better ratios of GREEDY than existing works on matroid constraint [Gatmiry and Gomez-Rodriguez, 2018] or submodular objective function [Friedrich et al., 2019].
In general, GREEDY works in round and at each round, an element of maximal marginal gain, whose addition does not violate partition matroid constraint, is added to the obtained solution. The algorithm terminates when the obtained solution is maximal. THRGREEDY, on the other hand, works by always keeping a threshold τ , which bounds the maximum marginal gain to the objective by any non-selected elements. The algorithm runs in rounds; at each round, any element with a marginal gain at least τ will be added to the solution if it does not violate the partition matroid constraint. After each round, τ is decreased by a factor 1 − ǫ in order to guarantee new elements can be added to the solution at successive rounds. The algorithm continues until the obtained solution becoming a maximal set or the threshold is below a value defined by ǫ and b. GREEDY's pseudocode is presented by Alg. 3 and THRGREEDY's is Alg. 4. Theorem 3. GREEDY obtains a min( 1 and has a query complexity of O(n b). Theorem 4. THRGREEDY obtains a min( 1 and has a query complexity of O( n ǫ ln b). Due to space limit, the full proof of Theorem 3 and 4 is provided in Appendix B.
In case of submodular objective function, r 2 of GREEDY is identical to the ratio obtained by [Friedrich et al., 2019]. With cardinality constraint, r (g) 2 matches with the ratio of [Bian et al., 2017], which was also proven to be tight. However, withb/b → 0 (e.g. the input is formed by many partitions), r for each i ∈ I and e ∈ V i \ S t do 5: if ∆ e f (S t ) ≥ τ then 6: Return S t

Applications and Experimental Results
In this section, we consider two applications of MAXMP: Boosting Influence Spread and Video Summarization.
Boosting Influence Spread. In this problem, a social directed graph G = (V, E) is given, where V represents a set of social network users; and E represents friendship between social users in V . An information will start spreading at a set I ⊂ V of users. The problem asks for a set S of users to strengthen the influence spread in order to maximize the number of users the information can reach.
Boosting Influence Spread under size constraint has been studied by [Lin et al., 2017]. In their model, each edge e = (u, v) ∈ E is associated with two weight values p 0 e , p 1 e (p 0 e ≤ p 1 e ≤ 1). The probability v adopts the information from u is p 1 e if v ∈ S; p 0 e otherwise. In this application, f (S) measures expected number of users the information can reach if S is selected. The authors has proven that f is monotone non-submodular; but did not show how close f is to submodularity. We provide the bound γ ′ , α ′ of γ and α of f as in Lemma 2, and full proof is provided in Appendix C.

Lemma 2. Given a Boosting Influence Spread instance, let ∆ be the maximum in-degree of the input directed graph. For any
Video Summarization Given a video, this application aims to pick a few representative frames from the video which can contains as much content as possible. The video contains n frames; each frame is represented by a p-dimensional vector. Let X ∈ R n×n be the Gramian matrix of the n resulting vectors and the Gaussian kernel; i.e. X ij is the value of the Gaussian kernel between the i-th and j-th vectors. The objective function is defined as f (S) = det(I + X S ), where X S is the submatrix of X indexed by S; and I is a unit matrix.
f (S) was proved to be supermodular by [Bian et al., 2017], thus its curvature α = 0. The authors also bounded the weakly submodular ratio, which is not useful in our algorithms. We bound the value of γ as in the following lemma, and full proof is provided in Appendix C.
and e ∈ V \ T :

Settings and Compared Algorithms
With Boosting Influence Spread, 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. For each edge e = (u, v), p 0 e = 1 dv and p 1 e = 2 dv where d v is in-degree of v. Information starts spreading at a node of highest degree. Due to lack of information, a user is randomly assigned to a group V i . The budget is distributed equally to each group, i.e. b 1 ≈ ... ≈ b k ≈ b k . The objective is estimated over 100 pre-sampled graph realizations of G.
With Video Summarization, we chose a video of roughly 3.5 minutes. The video is segmented to k equal-length parts; and the algorithms will pick b k frames from each part. With FASTPROB, we set δ = 0.001, which guarantees FASTPROB to return solutions almost similar to PROB but be much better in the number of queries. With THRGREEDY, we set ǫ = 0.5. Results were averaged over 10 repetitions.
We varied values of b and k; and compare FASTPROB, GREEDY and THRGREEDY with RES-GREEDY [Chen et al., 2018] and SPLITGROW [Buchbinder et al., 2019].
Although SPLITGROW's performance is unknown if f is submodular, we used it as a heuristic to compare. Source code is available at https://github.com/lannn2410/maxmp. In these experiments, FASTPROB, GREEDY and SPLIT-GROW performed approximately equal in term of solution quality while THRGREEDY was always the worst one. Especially, in Video Summarization, the supermodular objective function made the marginal gain of non-included elements increase with larger obtained solutions. Therefore, THRGREEDY easily reached a maximal solution just by one or two iterations of decreasing threshold. That explained why THRGREEDY took very few number of queries but has undesirable returned solution quality. In term of the number of queries, FASTPROB outperformed GREEDY, RESGREEDY and SPLITGROW. FASTPROB closed the gap or even surpassed THRGREEDY to become the best algorithm in the number of queries in the experiments with fixed b and varied k. In these experiments, we can see that the number of queries of all algorithms, except FASTPROB, almost did not change or just slightly decreased with larger k. FASTPROB's numbers, on the other hand, decreased significantly as k increased. This phenomenon is also reflected on the theoretical bound of FASTPROB's complexity. In Equ. (15), FASTPROB's complexity is bounded by

Numerical Results
With n i s are roughly equal (the same with b i s), FASTPROB's complexity becomes O(n ln b k ln b δ ), which decreases w.r.t k.

Discussion
We proposed PROB and later FASTPROB to solve monotone non-submodular maximization with partition matroid constraint. The experimental results demonstrated that FASTPROB can perform closely to the best algorithms in solution quality, and outperform other algorithms (except THRGREEDY-the worst in solution quality) in the number of queries. Although there is no superior algorithm in general, FASTPROB should be considered as the best algorithm in scenarios that scalability issues are concerned, e.g. algorithms with fast runtime and relatively high solution quality.
There is still an open question on what is the best algorithm in approximation ratio? PROB's ratio depends on γ ′ , α ′ -which can be undesirable in some settings of our experiments. However, it is unknown on how hard to obtain exact value of γ, α or other non-submodular quantities. And it is too expensive for us if computing those quantities by enumerating all possible S, T that T \ S satisfies partition matroid. Therefore, it is still open on how different between GREEDY, THRGREEDY, RESGREEDY and PROB's ratio. A Proof of FASTPROB's Ratio Similar to PROB, we prove that: In FASTPROB, with high probability (i.e. 1 − δ) there exists a way to construct a sequence of maximal sets S * 0 , ..., S * b that satisfies (1) S * 0 = S * and S

References
. If these three properties are guaranteed, the ratio of FASTPROB follows.
For each t = 0, ..., b − 1, a set S * t+1 is formed from S * t , S t and e t but with a condition that (S * t \ S t ) ∩ R t = ∅, which is guaranteed with high probability by Lemma 1.
Let's consider a moment when the t-th element is added into the solution. Let i be the index being considered when e t is added into S t−1 . With (S * t \ S t ) ∩ R t = ∅, let e ′ be an arbitrary element in (S * t \ S t ) ∩ R t , then S * t+1 is set as follows: where Equ. (21) is from properties of γ and α; while Equ. (23) is from AM-GM inequality.
which completes the proof.

C Omitted Proofs of Experiment Section
C.1 Proof of Lemma 2 A graph realization g of G is defined as a subgraph of G where edges' state were determined. Denote R g (I) as a number of reachable nodes from I in g. Given a boosted set H, the probability g is formed is given by where p H (e) = p 0 e if e = (u, v) has v ∈ H; otherwise p H (e) = ρ 1 e . Let G be a collection of all graph realization of G. We have: f (H) = g∈G ρ H (g) × R g (I) Given sets W, H that H ⊂ W and |(W \ H) ∩ V i | ≤ b i for all i ∈ [k], u ∈ W and a graph realization g. For each v ∈ W , any edge in form e = (w, v) satisfies p H (e) = p H∪{u} (e) and p W (e) = p W ∪{u} (e). On the other hand, any edge in form e = (w, u) will have weights that p H (e) = p W (e) = p 0 e and p H∪{u} (e) = p W ∪{u} (e) = p 1 e . Therefore, we always have p W ∪{u} (e) p H∪{u} (e) = pH (e) pW (e) and 1−p W ∪{u} (e) 1−p H∪{u} (e) = 1−pH (e) 1−pW (e) for all e ∈ g, which means ρW (g) ρH (g) = ρ W ∪{u} (g) We have: = g∈G ρ W (g) ρ H (g) ρ H∪{u} (g) − ρ H (g) × R g (S) The lemma follows by combining Equ. (38) and (41).

C.2 Proof of Lemma 3
For any set S, denote A S = I + X S . Given a set T , S ⊂ T and e ∈ T , we have: where the last inequality comes from Cauchy interlacing inequality. On the other hand, Therefore: which completes the proof.