Core-sets for Fair and Diverse Data Summarization
Authors: Sepideh Mahabadi
Stojan Trajanovski
Venue: NeurIPS 2023 poster (2023)
Keywords: Constrained Diversity Maximization
Fairness
Data Summarization
Core-sets
Approximation Algorithms
TL;DR: We propose novel core-set construction algorithms for producing a summary of the data which is both diverse and fair, along with experiments supporting our theoretical results.

Abstract: We study core-set construction algorithms for the task of Diversity Maximization under fairness/partition constraint. Given a set of points $P$ in a metric space partitioned into $m$ groups, and given $k_1,\ldots,k_m$, the goal of this problem is to pick $k_i$ points from each group $i$ such that the overall diversity of the $k=\sum_i k_i$ picked points is maximized. We consider two natural diversity measures: sum-of-pairwise distances and sum-of-nearest-neighbor distances, and show improved core-set construction algorithms with respect to these measures. More precisely, we show the first constant factor core-set w.r.t. sum-of-pairwise distances whose size is independent of the size of the dataset and the aspect ratio. Second, we show the first core-set w.r.t. the sum-of-nearest-neighbor distances. Finally, we run several experiments showing the effectiveness of our core-set approach. In particular, we apply constrained diversity maximization to summarize a set of timed messages that takes into account the messages' recency. Specifically, the summary should include more recent messages compared to older ones. This is a real task in one of the largest communication platforms, affecting the experience of hundreds of millions daily active users. By utilizing our core-set method for this task, we achieve a 100x speed-up while losing the diversity by only a few percent. Moreover, our approach allows us to improve the space usage of the algorithm in the streaming setting.

Core-sets for Fair and Diverse Data Summarization
Sepideh Mahabadi Microsoft Research Redmond, WA, USA smahabadi @mi emicrosoft.com com
Stojan Trajanovski" Microsoft London, United Kingdom sttrajandmi crosoff com
Abstract
We study core-set construction algorithms for the task of Diversity Maximization under fairness/partition constraint. Given a set of points P in a metric space partitioned into m groups, and given kı - km. the goal of this problem is pick k; points from each group i such that the overall diversity of the k = =, ky picked points is maximized. We consider two natural diversity measures: sum- of-pairwise distances and sum-of sum-of-nearest- -earest---inhrrrorr distances, and show improved core-set construction algorithms with respect to these measures. More precisely, we show the first constant factor core-set w.r.t. sum-of- of-paiiisse distances whose size is independent of the size of the dataset and the aspect ratio. Second, we show the first core-set w.r.t. the sum-of-nearest-n -eerest--niihhor distances. Finally, we run several experiments showing the effectiveness of our core-set approach. particular, apply constrained diversity maximization to summarize set of timed messages that takes into account messages' recency. Specifically, the summary should include more recent messages compared older ones. This is real task in one of the largest communication platforms, affecting the experience hundreds of millions daily active users. By utilizing our core-set method for this task, we achieve a 100x speed-up while losing the diversity by only a few percent. Moreover, approach allows to improve the space usage of the algorithm in the streaming setting.
Introduction
Data summarization problem is a class of tasks where small subset of items must be selected as a summary to represent the whole data. Typically in applications, the selected summary is required to fulfill various criteria such as diversity. In this paper, we focus on Diversity Maximization (DM) which is topic that has attracted significant attention 31, 30, 24, 19, 20, 25, 14]. The goal of this line of research is to provide a summary of a large dataset that preserves the diversity of the data much possible. This has many applications in various domains including summarization, recommendation systems, search, and facility location [15, 43, 40, 1, 5, 13. 2, 21, 39, 33]. Formally, in this task, given universe of n items, its goal is to choose a small subset of size k that maximizes a given pre-specified measure of diversity.
the past decades [11, 33, 3, 8. 9, 10,
Diversity Maximization under Partition Constraints is variant of the problem that has been studied to find a diverse summary while satisfying some additional orthogonal constraints [7, 31, 3, 28, 4, 10, 8, 9, 6, 26]. Here, the items in the input partitioned into disjoint groups P = P1 UP. and additionally, one given a pre-specified number of desired results from each group ki.... kms and the goal is return k; objects from each group P; such that the overall diversity among all k Σ, points is maximized. This formulation allows to control the number of objects from each category in the output, e.g., the number of movies from each genre shown user in recommendation system, or to bound the number of old messages included a summary of a user's feed. Moreover, this
*This equal contribution paper.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

formulation has been studied in the context of fairnsss (e.g. see [28, 4. 10]), where one wishes to control the number of results from each population in the produced summary. We will therefore refer to the Diversity Maximization under Partition Constraints as Fair Diversity Maximization (FDM), and use .i............ (P) to refer to the optimal achievable diversity under the fairness constraint. In this work, we consider fair diversity maximization with respect to three common diversity measures.
Diversity Measures. Several measures (or objective functions) have been proposed in the literature to model the notion of diversity [11, 3, 6, 25, 28, 9, 20, 16, 10, 31, 30J. A main category of such measures are based on pairwise distances (see [11] for complete list). In this work, we will consider measures: (1) the minimum--paine pairwise distance, where for a subset of points S _ P. their diversity is measured as the minimum pairwise distance between the points in the subset, i.c., mips dist (p. g): (2) sum-of pairwise distances between the weweoo--naaeettiigniiiee
three of the most common pairwise distance-basee
points in the subset, i.e., Σ P.qes dist (p. g): and (3) the interpolation between the first two measures, and is defined formally as Epes minges MMp dist g). We refer to these measures respectively as MIN- PAIRWISE DIST, SUM-PAIRWISE DIST, and SUM- NN DIST. All these three measures have been used previously to model diversity (e.g. see [11, 20, 6, 25], where they are respectively referred to as remote-edge, aamote-ciquee, and remote-pseudoforent In this work, we study Fair Diversity Maximization (FDM) over large datasets with respect to these three diversity measures.
distances which is an
Core-sets for Diversity Maximization. As one of the main applications of diversity maximization is related to data summarization, there has been a large body of work to solve diversity maximization in massive data models of computation, and in particular the design of core-sets [20, 19, 24, 27, 28, 8, 9, 41, 25, 26, 14). Core-set a small subset of the data which is sufficient for computing an approximate solution of a pre-specified optimization problem on the whole data.
More specifically, in this work we focus construction of composable core-sets[2O]: we present a summarization algorithm A that processes each group P. independently and produces small subset of it as its summary S; A(P.) S P. with the property that the fair diversity of the data is approximately preserved, i.c., divky....... k.......... km (S) 2 - .divk (P), where S is defined to be the union of all core-sets, i.e., S U, Sj. Composable core-sets are in particular useful for big data models of computation such as distributed and streaming settings as discussed in details in [20]. For example, in distributed setting where the dataset is partitioned over multiple machines based on groups, each machine can compute a core-set for its own dataset, and only send this small summary over to a single aggregator. The aggregator then processes the union of the summaries and outputs the solution. We provide further applications of the core-sets for processing timed datasets in the experiments sections of our paper.
1.1 Prior Work
Table I shows a summary of prior and our results.
Fair Diversity Maximization. Moumoulidou et al. [28] studied fair diversity maximization under MIN-PAIRWISE DIST and gave an (m) approximation algorithm for the problem. The bound was later improved [4] to m + 1. However, it is not known whether a linear dependence on m is necessary. In fact the problem admits an (1) approximation in the unconstrained version [17, 33]. For SUM-PAIRWISE DIST the problem admits a (1/2 + e) approximation [3, 7], which matches the performance of the best algorithm for the unconstrained diversity maximization. Finally, for SUM-NN DIST, Bhaskara et al. [6] presented a randomized ((1) approximation algorithm based on solving an LP for both DM and FDM.
Core-sets for Fair Diversity Maximization. Core-set construction algorithms for the unconstrained DM has been shown in [20] with respect all three diversity measures. For FDM, Moumoulidou et al. [28] showed that running greedy algorithm on each group independently provides core-set with a constant approximation factor, with respect to the MIN-PAIRWISE DIST. For the SUM- -MM-PAIRWISE DIST, Ceccarello et al. [8] provides core-set with the almost optimal (1 c) approximation factor. However, the size of the core-set depends on a parameter similar to the aspect ratio of the dataset. In particular, they show that for the case of doubling metrics, the core-set size could have exponential dependence on the doubling dimension. Under SUM-NN DIST, there has been no prior work on core-sets for FDM.
2

---

Table 1: The summary of prior and our results for FDM. Here l is the size of the solution and m is the number of groups. All the core-set results mentioned in the table have size poly(k).
MIN-PAIRWISE DIST SUM-PAIRWISE DIST
SUM-NN DIST
FDM Core-set for FDM
((m) [28. 4]
0(1 [3]
011) [6] O log k) Section 4
(1) [28]
((1) Section 2
1.2 Our Results
Theoretical results. We show the following theoretical results in this paper.
We show the first core-set construction algorithm for FDM under SUM-PAIRWISS DIST, with constant approximation factor whose size is independent of the number of points and the aspect ratio. In fact, we show a core-set of size only K? for each group P. that together achieve a constant factor approximation (see Theorem 2.1).
We also show the first core-set construction algorithm for the FDM under the SUM-NN DIST notion of diversity. We provide a core-set of size O(k2) ) for each group P; that together achieve an O(m- log k.) approximation factor (see Theorem 4.1). We remark that although the approximation factor is probably not optimal, we see in the experiments section that the algorithm performs well on real data.
To get the above core-set algorithm, we first show in Section 3, an approximation algorithm for FDM under the SUM-NN DIST. More precisely, we show an O(m² log k) approxima- tion with polynomial running time (see Theorem 3.4) and 0 - log k) approximation with an exponential runtime in k, (see Theorem 3.5). This algorithm might be of independent interest as the best previous algorithm by [6], despite having the ideal ((1) approximation, is randomized and based on solving an LP, whereas our algorithm is deterministic and based on a greedy approach (see Algorithm 1). In fact all of our algorithms are simple to implement and thus practical as we show next.
Finally, in Section C of the Appendices we show how to apply our results to the setting where the partitioning is not necessarily done according to the colors and thus get fully composable core-set for these notions.
Experiments. We perform experiments for all three diversity measures. Our first set of experiments uses FDM as a tool to account for recency in a summary computed on timed datasets. Here, we group dataset of messages by their created time. The goal is to compute diverse summary of the messages, where we additionally require to include less number of messages in the summary from the older batches of messages, and more from the recent batches. This is a real task in one of the largest commercial communication platforms. We get the following experiments and results.
First, we show that running diversity maximization algorithms without the group constraint does not satisfy our requirement and reports about equally number of old messages and the new ones.
Next, we compute the price of fairness (i.c., price of balancedness in this context), that is we compute how much we lose diversity by imposing the grouping requirement. Our experiments on Reddit dataset shows that the diversity only decreases by around 1% for sum-of-pairwiss distances; few percent up to no more than 20% for sum-of-NN distances and around 50% for minimum-pairwise. distances (due to its fragility) metrics.
We use the core-set construction algorithms to summarize each group first, and then run our diversity maximization algorithms on the union of the core-sets. Our experiments show that using core-sets, the runtime of our algorithm improves on average by factor of 100x while only losing diversity by few percent. We further remark that using core-sets in this context has an additional benefit: it removes the need to recompute the summary on the whole data when new messages arrive: once we summarize batch of old message, we no longer need to process the batch and only need to work with the core-set that is computed once.
We further show experiments that uses FDM as a tool for controlling the desired contribution of each genre in movie recommendation system.
3

---

Finally, we run experiments to compare our proposed core-set of Section 2 to the prior algorithm of [8] for core-set construction. We see that while the core-set produced by our algorithm on average smaller by factor of 200x, its performance is only worse by 1.3%.
1.3 Preliminaries
Throughout this work, assume that given point set P P1 P.....UUU in metric space (X, dist). Each point in P comes from one of the m groups in [m], which we also refer to as colors. We use P. to denote the points of color i. We use to denote [P] and n, to denote PP.). We denote the distance between two points p, by (p, q) and for a set of points S, we use dist(p, S) to denote minges (pst(p,.)) q).
1.3.1 Optimization problem
The optimization problem considered in this paper Fair Diversity Maximization as defined below. Definition 1.1 (Fair Diversity Maximization (FDM)), Given a colored point set P = U, P. and ki...., km the goal to pick subsets S; S P,, such that first |S k;, and second div(S) is maximized where S = U, S;. We will use di... (P) to denote the optimal diversity one can achieve this way, i.e.,
div( U S.) div ki........ke Am (P) S.SP P.... S. Pm [S Amm
We will use k to denote Σ, ki and thus |S| Definition 1.2 (Diversity Measures). For of points S, we consider the following diversity measures in this work i) MIN-PAIRWISE DIST: minp,ces dist(p, q): ii) SUM-PAIRWISE DIST: Ep.es dist(p, q): iii) SUM-NN DIST: Epes minges((p) dist(p.
1.3.2 Summarization task
The goal in our paper is to provide an intermediate summarization (i.e., a core-set) algorithm such that the union of the core-sets contains a good solution relative to the whole data. Let us formally define this notion.
Definition 1.3 (Core-set). Given point set P, subset T' is called an a-approximate core-set with respect to an optimization function f if the optimal value of f over T is within factor a of the optimal value of over P.
is desired that the size of the core-set is small. In this paper we focus on the optimization function being the diversity maximization function. Further, emphasize that our algorithm for constructing core-sets for P. processes each group P; independent of other groups. Therefore, provides a form of composability property as defined below.
Definition 1.4 (Color-Abiding Composable Core-set). An algorithm A is said construct an a- approximate color-abiding composable core-set, if it produces subset T; A(P.) C P. independent of the points other colors, s.t. diva,......... (T)) 2 diikk......... (P), where T = U,
Again, we note that although it is desireable that the size of the core-set [T: small, it does not necessarily need to be kg Later on, post-processing. algorithm on the union the computed core-sets, i.e., T to get final solution. However the focus of this work is on the core-set computation algorithm A.
can any exact or approximation
Throughout this work, for brevity we use composable core-set to refer to Definition 1.4. However, we remark that the above definition of color-abiding composable core-set is only applicable when points are partitioned based on the colors, and differs from the standard notion of composable core-sets defined in [20], where the partitioning is done arbitrarily. Later in Section C of the Appendices, we show how to employ our algorithms and get fully composable core-sets (that is not necessarily color-abiding) as defined in [20].
1.3.3 The GMM algorithm
In this work we will use the greedy algorithm of [17, 33] which we denote by GMM and depicted in Algorithm 1. Let us also state three well-known properties of GMM:

---

1. ry's are decreasing, i.e., for j > i, we have 2 ry.
2. For any < k; let S; {pi, , pi).. Then for any p E P\ St we have that dist(p, St) S
T+-1
3. Let T Ck P be any subset of k points in P. Then the minimum pairwise distance in T is
most 2 . Tk-
Algorithm The GMM Algorithm
Input point set P. and k Output subset = (Pi....,Pi } S P. and radii 71, "1,..,,
1: S f- an arbitrary point from P, and ri + 0o
2: for 2 to &: do
3: P: < the farthest point in P from S, i.e., argmax pddisttp S)
4: S SUpt
5: r; < minimum pairwise distance in S, i.e. ming dist(p1,
6: end for
7: return S
2 Core-set for FDM under SUM-PAIRWISE DIST
In this section we show algorithm for constructing core-set for FDM with respect to the SUM-PAIRME PAIRWISE DIST notion of diversity. Given a colored point set P= = Pi U...U Pm. and fi....,km,, the goal is to come up with core-set construction algorithm A that independently summarizes each point set P; and produces small subset it S = A(P;) S P. such that divk,...... km (S) 2 div (P), where again S = U, St-
Overview of the algorithm. Suppose that we want to find a solution that maximizes FDM under PAIRWII DIST notion of diversity. Consider the optimal solution OPT and let OPT, be the set of points from color Our algorithm for constructing a core-set proceeds by running GMM for k; iterations on P., to get seed of size k; It is then property of GMM that if each point mapped (i.e. moved) the closest seed in P., its distance does not change by more than r; (as defined in GMM). Now the points in different colors can have different and therefore the movements can be different scales. For two points p. g E OPT, if the scales of their movements w.r.t. their original distance are small, then the new distance is still large compare before. Otherwise, if the scale of these movements are large, we show how to charge the loss in the diversity of this pair onto other pairs that have relatively small movements. If there are not enough such pairs, can then show that the solution returned by the seeds themselves have had large diversity. Finally, in order to make the map injective (so that two points mapped to the same core-set point), for each of the seed points, the algorithm also stores in the core-set, the closest k; points to the seed, and thus increasing the size of the core-set k.?.
OPT; is
There is one hard case in the above approach and that is when h; = 1. In this case, the GMM algorithm can return any arbitrary point as the seed and that could provably be bad core-set. To handle this case, we show that is enough for the core-set algorithm to find at least a minimum of two seeds. Then show that it is always possible pick one of the seeds and get reasonably good approximation. This modification is proved to work in Appendix B.
Algorithm description. For simplicity, let us assume that for all i, we have k; 2 2. Otherwise, we show in Appendix B that slight modification of the algorithm works (although the proof becomes more involved). The core-set construction algorithm is shown in Algorithm 2. The algorithm proceeds by running GMM for k; iterations to compute set of k; centers. Then for each of these k; centers such p, the algorithm stores at most k; points from P. whose closest center among all K; centers is p.
Theorem 2.1. Algorithm 2 produces core-set with size O(k?) and a constant factor approximation:
dive km........ km (S) 2 J div di..,..... (P) for constant C. (Proof in Appendix A.
5

---

Algorithm 2 Core-set Construction Algorithm for SUM-PAIRWISE
Input point set P., together with parameters k; and (where h = h1 + km)
Output a subset S; S P:
1: S. {PI..... Pk. } + GMM(P,,
2: T 0
3: for E S do
4: for j=
k; do
5: T any point Pj E P. \ T s.t. argmin dist(pj, 9) =
6: end for
7: end for
8: S + S,UT
9: return S
3 Approximation Algorithm for FDM under SUM-NN DIST
As mentioned in the results section, in order to obtain our core-set construction algorithm under SUM-NN DIST in Section 4, first in this section we show an approximation algorithm for FDM under the SUM-NN DIST notion of diversity.
Overview of the algorithm. Consider the optimal solution OPT that maximizes FDM under SUM-NN DIST notion of diversity, and let OPT, be the set of points from color i. Now each point E OPT has contribution towards the diversity, i.e., dist(p, OPT \ {p}), and thus the contribution of each group OPT, towards the optimal solution is well-defined. Let us call the color with the maximum contribution as the most significant color. Clearly if we find solution SOL whose value least as large as the contribution of the most significant color, then we are within a factor of of the optimal solution.
Next, suppose that the most significant color is i and let d1 2 ... 2 de, be the contributions of the points in the optimal solution that are of color i. It is not hard to prove (as we will show later) that max, (j d,) approximates Σ/=1 dj up to a factor of log k. So we will construct a solution whose value is at least j dj and this will be within factor of (m- llog k) of the optimal solution promised.
More concretely, we will construct solution such that it contains j points of color i where no other point (from any color) lies within a distance dy of them (in reality, we find O(j) points such that no other point lies within a distance O(d,) them). Of course, we do not know i, j. and dy a priori. We can enumerate i and j. Further, if we run the GMM algorithm on color i for j iterations, then the minimum pairwise distance between the retrieved points is an approximation dj--
This itself is enough to pick O()) points of color that are (cl)) far from each other. Let us call these points the seeds. However, the remaining challenge is to pick the rest of the points (that the k Oj) points of color i, as well as ke points of color e for all l o i) away from these seeds.
This brings to the following problem: given colored point set / and a set of at most & balls B, how to pick the largest subset of balls B' C B, such that enough points exist outside of B'. (Note that B is basically the set of balls with radius Ody)), that are centered at the j points returned by the first j iterations of GMM). This problem can be solved exactly by an exhaustive search and spending exponential in k time. One can also get polynomial time 0(m) (5m))approximate solution for the problem by iteratively excluding half of the remaining balls from the solution, and at the same time satisfying the condition for half of the colors. Thus, after Olog m) iterations, all color constraints are satisfied, and a 1/m fraction of the balls remain. There are further technical details needed for the proof to go through which we need to take care of.
3.1 Algorithm Description
Given a colored point set P = U....U U and ki.... ......,,m..... the goal is to find a solution SOL SOL, J... USOL where SOL, C P,, and [SOL;] k, and that div(SOL) 2 divk, (P). The approximation algorithm is shown in Algorithm 3. The only unspecified part of the algorithm is in Line where we need to specify how we find the subset B' given the set of balls B. One can take different approaches resulting in different trade-off's described below.

---

Algorithm 3 Approximation Algorithm for FDM under SUM-NN DIST Notion of Diversity Input colored point set P = Pi U... U Pm and kı,..., km Output a solution SOL _ P where [SOL = kü with approximately maximum diversity
SOL t an arbitrary solution satisfying the color constraints, i... |SOL n P. k;
2: for E [m] do
3:
G, = {pI...... pt} + GMM(P; and let . be their corresponding radii.
4:
for to do
5:
Si...., Sm f-
6:
Let 2 be the largest iteration where (T() 2 r2/2 and let (()) - k if no such iteration
exists.
7:
Let B [Bi...., Big)} be the balls of radius rug/2 around the points ,i....,Pu. .P())
8:
Find an (approximately largest subset of balls B' S B such that P B' contains at least
k; BB|| points from color i, and least kę points from color & for each color o
9:
Add centers of B' to S Add an arbitrary set of K; - [3| points from P. B' to S; for & + i do
10:
11:
12:
Add an arbitrary set ke points from Ps \ B' to Se. end for
13:
U.S. S. is a valid solution and div(S) > div(SOL) then SOL 4 16: end
14:
i
15:
17: end for
18:
end for
19:
return SOL
3.1.1 Finding an optimal subset of balls (Line 8 of Algorithm 3)
Given a colored point set P and a set disjoint balls B, the goal here is to find an (approximately) largest subset of balls B' C B, such that
For a pre-specified color i [m]] we have |P,
B' k; |B"), B'|
* For all other colors é E [m]] \ {i), we have |P
2 ke-
Moreover, may assume that [ (()) S k. and that are interested only subsets B' of size upto JB|| S kg.
Approach 1. If the algorithm is allowed to spend exponential time in k; one can find the optimal subset B' in time & m as stated below.
Observation 3.1 (Approach 1). There is algorithm that finds the optimal largest subset B' C B in time ()) m = (O(s), (Proof in Appendix A.2).
Approach 2. One can get an approximate solution in polynomial time the number points of each color is sufficiently large, i.e, for each e [m)) we have n4 |P&l > 2 kiz Note that this is realistic assumption (also appeared in [11]), as we expect the number of data points to be much larger than the target size for the summary. Further, this assumption can be relaxed to ny being larger than constant times Kę similar to [11].
Lemma 3.2. There is algorithm that finds (( (a))aapprxximate largest subset B' in polynomial time, under the assumption that for each E [m), we have neg 2 2 lig (Proof in Appendix A.3).
3.2 Algorithm Analysis
Let us now describe the intuition behind Algorithm along with defining a set notations. Let OPT C P be the optimal solution and let OPT; OPT n P; be the points of color in the optimal solution. Moreover let di...., dz be the values of the optimal solution, i.e., d; = dist(pf, OPT (P) = div (iPT)
(1) where p) are the points in OPT, Therefore, we have that div Eism Ejst, dz.
7

---

Let 1" I m be the color with the maximum contribution in the optimal solution, i.e., i" arImaxiemml Ejsk, dj. Clearly, Ejsk, dj 2 div(OPT)/m Moreover, WLOG assume that for each i, dřj is are sorted, i.e., di 2 2 d,. Now, let j" be defined as ji) argmaxysk:) d). and define j" f
Claim 3.3. Let i E [m] be any color. Then we have ji) d')(() [lg((;++)) Ejst, dy. (Proof in Appendix A.4)
Theorem 3.4. Algorithm using Approach 2, runs in polynomial time and produces a solution with an approximation factor of (m log k). (Proof in Appendix A.5)
Similarly, running Algorithm with Approach I would give us the following theorem.
Theorem 3.5. There exists O(m log k) approximation algorithm that runs in time O poly(m, k)).
Core-set for FDM under SUM-NN DIST
In this section we show how to get a composable core-set for FDM with respect the SUM-NN DIST notion of diversity.
Overview of the algorithm. In order to construct core-set for FDM under the SUM-NN DIST notion of diversity, we show that is enough to construct subset of the points such that the solution to the problem of finding the maximum number of balls such that enough points exist outside of them (discussed in Section 3) remains unchanged. We show that the GMM algorithm has this property. Intuitively, since GMM chooses the points that pairwise-far from each other, many points are picked inside individual balls and thus the solution to the balls problem remains relatively unchanged. Therefore, if
the algorithm of Section the core-sets produced by GMM, the solution is similar as if we had run it on the whole data.
Algorithm description. In this section, the goal is to give summarization algorithm A that processes each dataset P. independently of other color datasets P, and produces a summary S = A(P.) such that di........... (S) 2 1 divki......... (P) where again S = U, S,. The core-set construction algorithm is simple and is shown in Algorithm 4. The algorithm proceeds by running the GMM algorithm times, and each time for k + iterations, and without replacement.
?
Algorithm 4 Core-set Construction Algorithm for SUM-NN
Input point set P, together with parameters kę and (where h ki + kim Output a subset S; C P.
I: S, 0
2: for j to le do
3: G, = {pl,..., Pk41] GM,(P.,
4: S, +- S.UG;
5: P. P.YG. Ge
6: end for
7:
return S;
Theorem 4.1. Algorithm 4 returns composable core-set of size Okk²) for each of the colors, with an approximation factor of O(m (lm--ogk)) k). (Proof in Appendix A.6)
Experiments
To demonstrate the effectiveness of our algorithms, we run simulations on public and timed datasets.
5.1 Tasks and Datasets
FDM as tool account for recency in a summary. Here the task is to produce a summary of set of timed messages with a property that (i) the summary is a diverse subset of the messages, and (ii) there are more recent messages shown the summary. We model this task by partitioning the messages into groups / colors based on their creation times and assign desired budget to each group.

---

We use a Reddit dataset [42] of text messages that are semantically embedded using BERT [12] into metric space. We also utilize message creation time stamps as we to show diverse, yet timely and relevant messages
user created across different time-we time-windan window intervals within certain period and thus assign color to each message based on to which time-window interval (e.g., a week, thus having 4 colors in total) the message creation time belongs to.
FDM tool for controlling the desired fairness contribution of each group. We further use FDM to control the contribution of each genre (besides time) in a movie dataset. Apart from the Reddit dataset, for this task we also use the MovieLens dataset [18] where the movie titles are semantically embedded into metric space. For this dataset, we have assigned movie to group represented by a color based on two criteria: movie genre, and (ii) the time-window interval the movie review creation time belongs to. We include the result of this dataset in Appendix D.2.
More details on the datasets preparation given in Appendix D. and additional result figures provided in Appendix D.2. We have also made the code of the algorithms publicly available'.
Nugber ooodggut frce a cale
Xumber contootts from ralor 11
Numben comignnte from coler
Jas toto 28to 31.0
Lio So 26
Colors (time period
Colors Hime period in d)
Colces (time period 4)
(a) Reddit (SUM-PAIRWA) PAIRWISE)
(b) Reddit (SUM-NN)
(c) Reddit
Figure DM algorithm outcomes for all colors (m with equidistant time period as fairness
colors in the Reddit dataset (k: 20 items).
5.2 Summary of the experiments and results
We run the following experiments using all three diversity measures.
Need for FDM. We first show why we need to resort to FDM. In particular, we show that if we run DM on the data, the results are not as fairly balanced as we want, as depicted Figure 1 and Figures 2 & (Appendix D.2.1). In the case of time periods colors dividing the data into colors (i.e., quarters within a month), for & = 20 DM algorithms give: (i) a certain color that is clearly dominantly present in the outcome (for all diversity distances), and (ii) this color not the one from the most recent messages (i.e., from the last color), see Figure for the Reddit dataset.
4
Price of fairness (balancedness)) Our next set of experiments show that when using FDM the diversity is not decreased by lot compared to DM. We use the loss diversity (% Div. loss) expressed as relative change of diversity distances as measure. This is shown in Table 2, and Tables & 5 (Appendix D.2.2). For most of these experiments we use the ofate-of-the-art algorithms. However for SUM-NN DIST 3 as an alternative to the LP-based randomized algorithm of [6]. When we run FDM, we gain in fairness (or balancedness). but we lose in diversity over the DM, expressed in different metrics. Experiments from Table show that we lose around 1 % for than 20% for SUM-NN DIST and around 50% for MIN-PAIRWY
proposed deterministic algorithm of Section
DIST; from few percent
DIST (due to its fragility) for various color distributions per group, while achieving the desired per group distribution, in both cases where enforce balancedness (i.e., uniform k;), and when enforce recency (i.e., k; increasing). The results also show similar trend if we use alternative message embeddings (Table 7 in Appendix D.2.4).
up
Effectiveness of our core-sets. We then show the effectiveness the core-sets. We run our core-set construction algorithms (of Section and Section 4) each color independently, get smaller size dataset. We then run the FDM optimization once on the union of the core-sets and once on the whole data. We also measure the loss of diversity and runtime improvement achieved by the use of core-sets. The results for all three measures are given in Table 3 and Table 6 (Appendix D.2.3). In

---

Table The loss of diversity (% Div. loss) between DM vs. FDM on the full data, expressed as a relative change, of the concerned SUM-PAIRWERS SUM-NN and MIN-PAIE PANN-PARIISE distances for uniform (upper part) or increasing (lower part) color values hy for the Reddit dataset.
DM vs. FDM
SUM-PAIRWIN SUM-NN MIN- PAIRWISE
colors k; Σ k; % Div. loss
Div. loss % Div. loss
22,2, 2,
8
1.22%
9.66% 14.27%
51.57%
3,3,3,
12
0.98%
49.99%
4,4,4,4
16
0.50%
13.72%
78.78%
5,
20
0.47%
18.96%
48.05%
6, 6
24
0.19%
9.48%
47.20%
8,84,688
20
0.42%
15.40%
48.05%
8,6,9.12
0,29%
13.29%
46.34%
[4. 12,
40
0.25%
1.98%
45.52%
5, 10, 15, 15
50
0.16%
9.62%
44.48%
6, 12, 18, 24
60
0.12%
3.98%
43.60%
terms of diversity loss, the results show the diversity values are on-par or with marginal difference we apply the FDM the union of core-sets, compared to FDM applied to the full data. (In the case of SUM-NN DIST, there cases where one is marginally better than the other, due to higher approximation factor.) Our experiments show that using core-sets, the runtime of our algorithm improves average by factor of few 10x 100x, while only losing diversity by few percent. We remark that using core-sets this context has an additional benefit: removes the need to recompute the summary the whole data when messages arrive: once summarize batch of old message, we no longer need to process the batch and only need to work with the core-set that is computed once.
Table 3: The loss of diversity (% Div. loss) expressed relative change of diversity distances, and the rumning time gains (x times faster) of the FDM when applied to the union of core-sets compared to FDM applied the full data for uniform increasing color values k; for the Reddit dataset. We remark that the results for MIN- MIN-PAIRWIS have % Div. loss being 0% as for this data the two points connected with the minimum distance always end up in the union of the core-sets.
FDM full data core-sets
SUM- HIMMPAIRWISE
SUM-NN
MIN-PAi PAIRWISE
colors k;
Σ ha % Div. loss
Time gain (x) & Div. loss
Time gain (x) % Div. loss
Time gain (x)
2, 2, 2,
1.35%
196.24 24
2.22%
769.70
0.00%
208.64
3, 3,3,33 3
12 0.67%
333.13
0.29%
888.55
0.00%
152.48
4,4,4,4
16
1.21%
539.69
-1.59%
474.26
0.00%
122.29
5, 5,5,5, 5,5
20
1.17%
432.68
-0.44%
294.23
0.00%
89.08
6, 6,6
24
0.94%
130.87
-3.03%
183.28
0.00%
63.69
2, 6.
20
1.50%
845.98
-1.80%
285.66
0.00%
91.44
(3,6.9.
30
1.06%
134.76
2.27%
110.36
0.00%
53.05
[18. 12,
40
1.02%
182.06
-0.88%
57.88
0.00%
36.51
10,
15. 20
50
1.16%
194.36
0.71%
31.90
0.00%
26.97
6. 18,
12,
24
60
1.27%
172.25
-0.49%
23.71
0.00%
20.53
Comparison to state-of-the-art core-set algorithm for SUM-PAIRWISE DIST. Finally, we compare the core-set construction algorithm in [8] for SUM-PAIRWISE DIST to our algorithm of Section 2. Appendix D.2.5 show that, the size of the core-set obtained by the algorithm in [8] for getting factor 2 approximation is close the data size in practice. In addition, the final diversity loss of our algorithm negligible (less than 1% to few percent) even though produces much smaller core-set. Further, our core-set construction algorithm is also significantly faster.
The experiments
10

---

References
[1] S. Abbar, Amer- Yahia, P. Indyk, and S. Mahabadi. Real-Time Recommendation of Diverse Related Articles. In Proceedings of the 22nd International Conference World Wide Web (WWW'13) pages 1-12, 2013.
[2] Abbar, S. Amer- Yahia, P. Indyk, S. Mahabadi, and K. R. Varadarajan. Diverse Near Neighbor Problem. In Proceedings of the twenty-ninth annual Symposium on Computational Geometry (SoCG'13) 13), pages 207-214, 2013.
[3] Z. Abbassi, V. S. Mirrokni, and M. Thakur. Diversity Maximization Under Matroid Constraints. In Proceedings of the 19th ACM SIGKDD International Conference Knowledge Discovery and Data mining, pages 32 42- 2013.
[4] R. Addanki, McGregullr, Meliou, and Z. Moumoulidou. Improved Approximation and Scalability for Fair Max-Min Diversification. arXiv preprint arXiv:2201.06677. 2022.
[5] A. Angel and N. Koudas. Efficient Diversity-Aware Search. In Proceedings of the 2011 ACM SIGMOD International Conference on Management of Data, pages 781 781-792, 2011.
[6] A. Bhaskara, M. Ghadiri, V. Mirrokni, and O. Svensson. Linear Relaxations for Finding Diverse Elements in Metric Spaces. Advances in Neural Information Processing Systems (NIPS' 16), 29, 2016.
[7] A. Borodin, H. C. Lee, and Y. Ye. Max-Sum Diversification, Monotone Submodular Functions and Dynamic Updates. In Proceedings of the s ACM SIGMOD-SIGACTTSSIAA symposium on Principles of Database Systems, pages 155-166, 2012.
[8] M. Ceccarello, A. Pietracaprina, and G. Pucci. Fast Coreset-based Diversity Maximization under Matroid Constraints. In Proceedings of the Eleventh ACM International Conference on Web Search and Data Mining, pages 81-89, 2018.
[9] M. Ceccarello, A. Pietracaprina, and G. Pucci. A General Coreset-Based Approach to Diversity Maximization under Matroid Constraints. ACM Transactions on Knowledge Discovery from Data (TKDD), 14(5):1-27, 2020.
[10] E. Celis, V. Keswani, D. Straszak, A. Deshpande, T. Kathuria, and N. Vishnoi. Fair and Diverse DPP-Based Data Summarization. In International Conference on Machine Learning (ICML' pages 716-725. PMLR, 2018.
[11] B. Chandra and M. M. Halldórsson. Approximation Algullrithms for Dispersion Problems. Journal of Algullrithms, 38(2):438-465, 2001.
[12] J. Devlin, M.-W. Chang, K. Lee, and K. Toutanova. BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding. In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Tech- nologies, Volume I (Long and Short Papers), Minneapolis, Minnesota, June 2019. Association for Computational Linguistics.
[13] M. Drosou and E. Pitoura. Search Result Diversification. ACM SIGMOD Record, 39(1):41-47 2010.
[14] S. Gollapudi, S. Mahabadi, and V. Sivashankar. Composable coresets for determinant maxi- mization: Greedy is almost optimal. In Advances in Neural Information Processing Systems (NeurIPS),
[15] S. Gollapudi and A. Sharma. An Axiomatic Approach for Result Diversification. In Proceedings of the 18th International Conference on World Wide Web (WWW'09) 099, pages 381-390, 2009.
[16] B. Gong, W.-L. Chao, K. Grauman, and Sha. Diverse Sequential Subset Selection for Supervised Video Summarization. In Advances in Neural Information Processing Systems 27 (NIPS 2014), 27, 2014.
[17) T. Gonzalez. Clustering to minimize the maximum intercluster distance. Theoretical Computer Science (TCS), 38:293-306, 1985.

---

[18] F. M. Harper and J. A. Konstan. The MovieLens Datasets: History and Context. 5(4), dec 2015.
[19] P. Indyk, S. Mahabadi, S. O. Gharan, and A. Rezaei. Composable Core-sets for Determinant Maximization Problems via Spectral Spanners. Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '20,, pages 1675-1694, SIAM, 2020.
[20] P. Indyk, S. Mahabadi, M. Mahdian, and V. S. Mirrokni. Composable core-sets for Diversity and Coverage Maximization. In Proceedings of the 33rd ACM symposium on Principles of database systems, pages 100-108, 108, 2014.
[21] A. Jain, P. Sarda, and J. R. Haritsa. Providing Diversity in K-Nearest Neighbor Query Results. In Pacific-Asia Conference on Knowledge Discovery and Data Mining, pages 404413. Springer, 2004.
[22] B. Kim, H. Kim, and G. Kim. Abstractive Summarization of Reddit Posts with Multi-level Memory Networks. In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume I (Long and Short Papers), Minncapolis, Minnesota, June 2019. Association for Computational Linguistics.
[23] Y. Liu, M. Ott, N. guoyal, J. Du, M. Joshi, D. Chen, O. Levy, M. Lewis, L. Zettlemoyer. and V. Stoyanov. RoBERTa: A Robustly Optimized BERT Pretraining Approach. arXiv preprint arXiv: 1692, 2019.
[24] S. Mahabadi, P. Indyk, S. O. Gharan, and A. Rezaei. Composable Core-sets for Determinant Maximization: A Simple Near-Optimal Algorithm. In International Conference Machine Learning (ICML'19) pages 4254-4263. PMLR, 2019.
[25] S. Mahabadi and S. Narayanan. Improved diversity maximization algorithms for matching and pseudoforest. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM), 2023.
[26] S. Mahabadi and T.-D. Vuong. Composable coresets for constrained determinant maximization and beyond. arXiv preprint arXiv:2211.000 1.00229, 2022.
[27] V. Mirrokni and M. Zadimoghaddam. Randomized Composable Core-sets for Distributed Submodular Maximization. In Proceedings of the serty-seventh annual ACM Symposium on Theory of Computing 15), pages 153-162, 2015.
[28] 7. Moumoulidou, A. Mc Gregor, and A. Meliou, Diverse Data Selection under Fairness Constraints. arXiv preprint arXiv:2010.0914/ 2020.
[29] J. Ni, G. Hernandez Abrego, N. Constant, J. Ma. K. Hall, D. Cer, and Y. Yang. Sentence- T5: Scalable Sentence Encoders from Pre-trained Text-to-Text Models. In Findings of the Association for Computational Linguistics: ACI. 2022, Dublin, Ireland, May 2022. Association for Computational Linguistics.
[30] A. Nikolov. Randomized Rounding for the Largest Simplex Problem. In Proceedings of the forty-seventh anmual ACM symposium Theory of Computing (STOC'15), pages 861-870, 2015.
[31] A. Nikolov and M. Singh. Maximizing Determinants under Partition Constraints. In Proceedings of the forty-eighth annual ACM symposium on Theory of Computing 16), pages 192-201, 2016.
[32] J. Pennington, R. Socher, and C. D. Manning, GloVe: Global Vectors for Word Representation. In Empirical Methods in Natural Language Processing (EMNLP), pages 1532-1543, 2014.
[33] S. S. Ravi, D. Rosenkrantz, and G. K. Tayi. Facility dispersion problems: Heuristics and special cases, In Workshop on Algorithms and Data Structures, pages 355-366. Springer, 1991.
[34] N. Reimers and I. Gurevych. Networks. In Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing (EMNLP). Association for Computational Linguistics, 11 2019.
BERe:: Sentence Embeddings using Siamese BERT-
12

---

[35] K. Song, X. Tan, T. Qin, J. Lu, and T.-Y. Liu. MPNet: Masked and Permuted Pre-training for Language Understanding. In H. Larochelle, M. Ranzato, R. Hadsell, M. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems (NeurIPS), volume 33, pages 16857-16867. Curran Associates, Inc., 2020.
[36] N. Thakur, N. Reimers, J. Daxenberger, and I. Gurevych. Augmented SBERT: Data Augmenta- tion Method for Improving Bi-Encoders for Pairwise Sentence Scoring Tasks. In Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Online, June 2021. Association for Computational Linguistics.
[37] M. Völske, M. Potthast, S. Syed, and B. Stein. TL:DR: Mining Reddit to Learn Automatic Sum- marization. In Proceedings the Workshop New Frontiers in Summarization, Copenhagen, Denmark, Sept. 2017. Association for Computational Linguistics.
[38] W. Wang, F. Wei, L. Dong, H. Bao, N. Yang, and M. Zhou. MiniLM: Deep Self-Attention Distillation for Task-Agnostic Compression of Pre-Trained Transformers. Larochelle, M. Ranzato, R. Hadsell, M. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems (NeurIPS' 20), volume 33, pages 5776-5788, 2020.
[39] M. J. Welch, J. Cho, and C. Olston. Search Result Diversity for Informational Queries. In Proceedings of the 20th International Conference World Wide Web (WWW'I1), pages 237-246, 2011.
[40] C. Yu, L. V. Lakshmanan, and S. Amer-Yahia. Recommendation Diversification using Explana- tions. In 2009 IEEE 25th International Conference on Data Engineering, pages 1299-1302. IEEE, 2009.
[41] S. Zadeh, M. Ghadiri, V. Mirrokni, and M. Zadimoghaddam. Scalable feature selection via distributed diversity maximization. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 31, 2017.
[42] H. Zhu, F. Nan, Z. Wang, R. Nallapati, and B. Xiang, Who did They Respond to? Conversation Structure Modeling using Masked Hicrarchical Transformer. arXiv preprint arXiv:1911.1066 (AAAI220,, 2019.
[43] C.-N. Ziegler, S. M. McNee, J. A. Konstan, and G. Lausen. Improving Recommendation Lists Through Topic Diversification. In Proceedings of the 14th International Conference on World Wide Web (WWW'05), pages 22-32, 2005.
13

---

A Deferred Proofs
A.1 Proof of Theorem 2.1
Proof. First note that it is easy to see that the size of each S; is at most k..
We will then show that the approximation factor is O(1). Let OPT; OPT n P. be the points of color in the optimal solution of P. For each color E [m]] let us use r, to denote the minimum pairwise distance between the set of k; points returned by GMM k;) in Line of the algorithm. Further let us abuse the notation, and for point E P. use yy to denote Tez where Ca E [mn] is the color of the point x.
Now let us also divide the optimal value of the diversity into two parts.
div(TPT)
E
dist( y)
Σ
dist y)
N.EEPP:: dist( max(reiry)
2.PEPPT: dist( w125 (r.in))
Let A := Σ yyEOPT: dist(z,)) <3 (rairg) dist(z, y) be the first term in the above summation and dist(x, y) denote the second term. Now we consider two
B = Σ LE.PEPPT:
cases separately.
Case 1: A B. In this case we have that
diP(TP < A
Σ
5 max(r S 20
Σ
S 20 -
Σ kp
R.УEOPT
Z.PEPPT
<E[mi
Now let us define a solution as follows. Let SOL; S S; be the first set of k; points added to S; in Line 1 of the algorithm using GMM. Then clearly the overall diversity of this solution is at least
div(SOL)) = Σ Σ
dist (x, 4) +
Σ
Σ
E ZESOL.
dist (z, y)
2
kE[m) R.yESOL,
&E smmm]
yESOL
r3 Σ
E
(k:
T4
by the triangle inequality
[E(m]
iE/m] yESOLASOL,
Kis
ki
ri
(k: k::)
ml
k2
Ki
kiTs
rs(
4
2
1m(m]
(e(m)
kin
1E(m)
where get the last inequality, we used the fact that for k; > the second term is non-negative. Therefore div(SOT.) 2 80 ddivOOPT.
Case A< < B. this case we have that div(OPT) S 2B. We will show how to choose the solution SOL. Let OPT, = OPT n P. as before.
Observation A.1. There exists a one-to-one mapping ОPT, + S₁ s.t. for each E ОРP, dist(o, p(o)) < 2r,,
Proof. Let S St be the first set of k; points added to Sj in Line 1 of the algorithm. For point p E P; let (p)) = eeg
be the nearest center in Sy to p. Also, for center s' E St let NNss) = {s E S; n(s) = s'} be the set of points in the core-set whose nearest center in S is s', i.e., the points that have been added the core-set in Line of the algorithm while processing
s'. Finally let D(s') (o E OPT,: n(() = 8') be the set of points of color i in the optimal
solution whose closest center in S' is s'. Note that because JOPT, = k; we have [N(s')] 2 ID(s'), as the algorithm keeps adding points to S; as long such point exists, and fewer than k; points
14

---

have been added to (s'). Therefore, we can always find a matching between D(s') and (s') of size least [s(s'), Thus such μ exists that maps a point o E D(s') to its match (sss). By Property 3 of GMM we know that dist(o,,s) x') S and (s', I Ti, and thus we get that dist(o, mlo)) s 2r;-
Now define SOL, _ St to be (u(o): o OPT,) and clearly |SOL;] = kū Then we have
div(SOL.) >
Σ
dist dist(u((),
=:PEPP: dist dist (2.0)) (r
Σ
dist(a, y) dist(z, p(x)) dist(y. pvv))
T.yEPP: (z,)(2, ma
M
Σ
dist (I. y) 2r 2r
2.PEPPT dist (2,9) max
Σ
dist(x, 2)/5
T:PEPPT: (2))( mr 2 B/5 2 diP(OP1
A.2 Proof of Observation 3.1
Proof. One can brute force on each possible subset B', and count the number of points from each color that falls in B', and thus compute the number of remaining points for each color, |P; B' in O(IB" m) time and check whether the number exceeds kgg So the total runtime is at most E kr
(1)) 2 m) S k R
A.3 Proof of Lemma 3.2
First one can check if there exists a subset B/ of size 2 = 0(1) in polynomial time using Approach 1.
Proof.
Next we construct solution Bj. For each E [m]] let de = kg be the demand of color f, that is the total number of points of that color which we want to exist outside of our solution B, First WLOG we assume that all points of P lie inside one of the balls in B (if this is not the case, one can subtract the number of points of each color that are outside of all the balls from the demands de). Then start with B₁ B and repeat the following process as long as there are non-zer demands left.
We let A be arbitrary subset of half of the balls in B₁ and let Ā = B1 \ A.
Note that for each color 8 [m] with non-zero demand de O. either A or Á contains at least de points of color E in them. This is initially true as one of A or A should contain half of the points that is nt/2 2 loz 2 de. We show this remains true at the end of the process.
Let LA be the number of colors é E [ml] with non-zero demands (i.e., de > 0) such that A contains more points of color E than A, and define l similarly as the number of colors f [m]] with non-zero demands such that À contains more points of color than A.
Now we let B₁ A if f 2 L and let Bi = A otherwise. This ensures that the demand of at least half of the colors with non-zero demand has been satisfied as the set we are excluding from B, satisfies the demand of at least half of the colors with non-zero demands. This means that the total number of iterations is at most log m.
We will update the demands of all the colors based on the set that was excluded from Bi. WLOG assume that L t.- Then for each E that de > set de max de [A n Pel).
Let l be color that has still a non-zero demand. Note that this means that IAn Pa S de. Therefore we will still have the property that |An Pt [B \ n > 2d
15

---

An 2 2(d Pt) where here we used B1 and de to denote their values before we apply the update corresponding to this iteration.
Finally, we return the best of Bo and B1 as B', i.e., the one with maximum size. Note that if OPT I 2m, then Bo itself is an (m) approximation. Otherwise, if OPT 2m, then the total number of iterations obtain B1 is at most log m, we have |B'| OPT/m.
B1 N B /22og m |BImm²
A.4 Proof of Claim 3.3
Proof. Divide the interval [1, kjj into logarithmically many number of intervals such that for each
1 S 8 < [lgg(;; + 1)], Le = [2--1, min h; + 1}). Then for each we have that
Σ JEL
d S 2 dz-- (1) -d)
and therefore, Ejsk, dz z [log(k; ; + 1)] 1)1 -5 d3-60-
A.5 Proof of Theorem 3.4
Proof. First note that, it can easily checked that the algorithm runs in polynomial time by Lemma 3.2. Next, consider the iteration of Algorithm 3 corresponding to i and where i = i* and j is chosen as follows,
1. j is the largest value in the range j S S k such that ry 2 dzj
2. If no such exists, we let j = jr
3. Finally, if <j le and rj+1 dzf- /2, increase j by one, i.e., j
In all the above cases, either by Property 3 of the GMM algorithm, or by definition, we have that ry 2 dz./2 Therefore, T(()) 2 d5./4. Therefore the balls in B defined in Line 7 of the algorithm, have radius at least /8./8.
Claim A.2. Let B" C B be the maximum size subset of the balls s.t. P B" contains K; [ points of color i, and at least ke number of points from color f, for each + i. Then [B"| 2 j
Proof. Note that OPT,- contains subset R j points from P.. such that there are no other points from OPT the ball of radius dy- around the points R. Now, we consider three cases separately.
Case j k. Note that in this case also have that t(j) k. Therefore, B contains & disjoint balls. Obtain B" from B as follows. First set B" = B. Then for each color & * remove at most kę balls from B" that contain the points of color E in the optimal solution. Since B has size k Ee ke. in the end B" will have size at least K; 2 j
Case 2: j < k and ((j) h. Again in this case B contains & disjoint balls and one can obtain B" with size at least j similar to the above case.
Case 3: j < l and t()) < k. For this case, let us first prove the following simple claim.
Claim A.3. T(G)+1 < d
Proof. First note that by the definition of t(j), we know that T(0)+ T2/2. Now if we have
Tj S dy. (this happens when we increased the value of j in the last step), then we have that T10)+ <r,/2 < dz., /2 and the claim is proved. Otherwise, it means that rj+1 dz. /2 (since we did not increase j in Item 3). But then since ((j) 2 we have that (()) + 2 + 1. Therefore, Ti0+1 df /2 and the claim is proved again.
16

---

Therefore, all the points in P lie within distance of at most Fx < / of one of the centers of the balls in B. For each point & E R let N (q)) be the closest center among the centers of B to q. Note that for two points 91.92 92 E R. ((1)) # ((2) as otherwise their distance is less than + < dz- contradicting the definition of the set R. Let B" be the subset of the j" balls centered at (R). Note that for any other point the optimal solution, i.e., q E OPT ' R, it cannot lie inside any of the halls in the subset B", as again it contradicts the definition of R. This means that the set P \ B" contains enough points: i.., K - [t] points from color i, and ke points from color for each E + i.
Therefore, having Claim A.2 and using Lemma 3.2, we get that [B') /m. Now, let St...., Sm be the solution created at the iteration corresponding to i and j as specified above. That is, S. contains the centers of the balls in B' returned by Approach 2, together with an arbitrary set of k; [3' points from P: \. B'. Further, for each E o i, let Sy contain an arbitrary set of k2 points from P. \ B'. This solution contains a set of [B] 2 j" /m points such that no other point in S lies within a distance of r22)/2 2 /f./8. /8. Now, to see the approximation. note that
div(SOL) 2 div(S)
(5 /m) djj//en by what we just proved
Σ dz
by Claim 3.3
m 41 [lg((ss- + 1)]
j'sk-
ΣΣ dz S'
by choice of 1
m² c [log(ks + 1)]
1
m² 61 -log div(OPT)
by definition of dz's
A.6
Proof of Theorem 4.1
Proof. We show the lemma by comparing the result of running Algorithm 3 on the union of the core-sets S = U. and running it on the whole dataset P U, P.. In particular, in Line 3 of Algorithm 3, rumning the GMM algorithm on St would return the same set of points as running on P., St itself contains G, Therefore, both runs of the algorithm end with the same set of balls B. We will now show the following claim.
Claim A.A. Let B be set of at most k disjoint balls of radius r/2 such that there exists subset B' C B of size at most B'| < k of them such that Pt \ B' contains ke points. Further let C be a set of B balls with the same centers as but with radius r/6 instead, and let C" C C be the subset of them corresponding to B'. Then Se \ C' contains ke points.
Proof. Note that Se is the result of running the GMM algorithm & times on Pt each for k+ iterations. Now, for i < k, let use T to denote the set of k + 1 points returned by the ith run of GMM. Thus, T' is the result of running GMM on the set Pe Ujóc' T3. Let r' be the minimum pairwise distance between the points in T Now if for all i < ke, T" contains at least one point outside of the balls in C" then clearly Тe contains kt points outside C" and the claim is proved.
Otherwise consider the first iteration i such that T C C". This means that since |T'| k - 1 and IC'| = |B'| < k. there exists pair of points in T" whose distance is at most 2 r/6 = r r/3. But then by Property 2 of GMM, this means that all the other points in Pt \ Uj T are within a distance of r/3 from one of the balls in C' and therefore, they are all within B". This means that Ps \ B' can only contain points from Ufes T C Sr, and thus the lemma is proved.
This means that if we replace the set of balls B in Algorithm 3 with C, both Approach and Approach 2, will be able to find the set C' (either exactly or approximately depending on which Approach we use). This means that corresponding to each solution SOL. found by Algorithm 3 2, there will be a corresponding solution in the core-set of diversity at least dSv(L))) (as the radius of the balls in
17

---

C' 1/3 of the radius of the balls in B). Therefore, as Theorem 3.5 shows that using approach 1, one gets a solution with approximation factor of (m log k), then this means that Algorithm 4 provides composable core-set of size O(k2) for each color, with an approximation factor of ( log k.). IT
B Generalization of Section 2 to the case where k; 2
In Section 2 of the paper, for simplification of the proof, assumed that for all i, we have k > 1. Here, we remove this assumption. and show that a simple modification the algorithm works even for some i's we have K; = 1. The modified algorithm is shown in Algorithm 5. The only modification made is that in Line 1, the GMM will be run for at least two iterations even if k; 1.
Algorithm 5 Sore-set Construction Algorithm for SUM-PAIRWISS
Input point set P; together with parameters kę and (where k: = kis + kim) Output a subset S, P.
1: S: (PI.
Pk. + GMM max (ki, 2})
2: T <
3: for E S; do
4: for j =
k; do TU the closest point Pj E P. I't p.s.sss...... s.t. argminges, dist(p,, 9) p.
5:
6: end for
7: end for
8: UT
9:
return S:
Theorem B.1. Algorithm produces a core-set with size (kk)) and a constant factor approximation:
div.y......... k.. (S)= 2 C divkk......... (P) for a constant c.
Proof. Again is easy see that the size of each Sy is at most k. and we only need show that the approximation factor is O(1). We use the same notation as in the proof of Theorem 2.1. Note the only modification that now for colors with k; 1, we have that r; is the distance between the two points in S; returned by GMM P., max max 2}) in Line I of the algorithm. Again, divide the optimal value of the diversity into two parts A and B defined as before. Again we consider two cases separately. The case of A < B (i.e., Case 2 in the proof of Theorem 2. I), holds similar to before. So we only need to prove the case A 2 B, which we show below.
In this case as before, we have that (OPT) < 20 k Eie(m) kyTt.
Now let us divide the colors into two groups based on the value of their k; i.e., let G = {ē: k; > WLOG, let rename the colors so that the first |G] colors of [m]] are the colors in G, and moreover, colors |C| 1 to m are sorted such that rj S T whenever |G| + S jı < j2 S m. Finally, we define Σjgia ky to be the total number points in any solution that are from groups with at least one point in them.
and thus [m] \ G will contain colors with
Constructing the solution. Now let define solution follows.
For GG]. define SOL, S; before, be the first set of k; points added S; in Line of the algorithm using GMM. Let SOL Uleo SOL; be the union of all these solutions.
To define SOL, for |G| + 1 i S m, note that k; = 1, and thus we need to decide which of the two points added in Line 1 of the algorithm to S, should be picked in SOL, Note that these two points are at distance exactly r;.
We go over the colors |G| + 1 to one by one and decide which of the two points to choose for SOL;- When at color i, let Pt, p. E S, be the two points returned in Line I of the algorithm using GMM which are at distance T; from each other. We let SOL, {pr} if ExeU,e: SOL, dist(x, p.) 2 ExeU, SOL, dist(r, p!), and let SOL; = {n{} otherwise.
18

---

This way of constructing the solution gives us the property that
dist(æ, 2 7i 2 (++i-1-|G))
DEU SOL,
where abused the notation SOL, to refer the only point in SOL,
Analysis. To show that the constructed solution has large diversity, let us divide the participating distances into three parts below.
div(SOL)
Σ
dist(r, y) +
Σ
dist y) +
Σ
dist(z, y)
Z.yESOLG
#ESOL .ESOOL
E.DESOL SOL
Let us refer to the above three terms as divi, div2, and div3. Now by the construction of SOL; for i I [G], similar to Case the proof Theorem 2.1, one can show that
k Σ
divi + div 2
km
4 $
G
Claim B.2. dive divs
E G+= Po.
Proof.
Note that we have
diva + div3
Σ
dist( v)
Σ
#H SOLA ASOLSSSSOLLLLLLLLLL yESOL
|G|+1
Now we consider cases separately, if k/2 then clearly (L+i 1- GI) > k/2 f GG and we have
div, + div3 2
Σ
Pi 2
(t+i-
|G|)
>
2 2 i=|G|+
G=|
t= G|
Otherwise, if < k/2 then since we assumed that the r; for |G| that the last term in the summation is fm
+ 1 <is < m are sorted, and noting
2 (k- 1), we have
div: + divy =
Σ
m
Ts
-t+i-
GG) Z
Σ
Σ
m
P:
k
r;
2
2
2
8
i=|0|+1
t=
h/2
1=
k/2
1=
G1+1
Thus, noting that k; for i |G| and using the upper bound stated div(OPT), we get that
1 k
k
m
div(SOL) div, + dive div3
Σ kiT
Σ ki
N Σ kRr: 2 div(OPT)
2
320
|=|G|+1
C Arbitrary Partitioning and Fully Composable Core-sets
In this section, we show what our results imply when the partitioning of the point sets into multiple parts not necessarily based on the colors. This will provide composable core-set as defined in [20] as opposed to the color-abiding composable core-set as defined in 1.4.
19

---

Proof. The algorithm simply runs Algorithm 4 for each of P; and returns their union. The size of the core-set is clearly Σism k2 < mkk O(k)). Moreover, by Theorem 4.1 it is again easy to verify that this is in fact a composable core-set, because for any collection of colored point sets p(1), P(N), again one treat them having N different groups with x,4) S ki Again, although one does not know the values of k: at the time of running Algorithm 4, however since k(9) < kig it is easy to verify that the point set picked by running Algorithm on p(f with parameter Formally, the goal is to present summarization algorithm A that now receives a colored point set P Uigm P. and the goal is to summarize it into C with the following composablility property. For any collection of colored point sets p(t), .., p(X), we have that
div divki.... &mm (U A(Pl)))) - divii,.. Am p()) JSN
1
ISN
Corollary C.I. have an algorithm that given a colored point set Uism P; computes (not necessarily color-abiding) composable core-set of size k2 for the Fair Diversity Maximization problem under the SUM-PAIRWISE DIST notion of diversity.
Proof. The algorithm simply runs Algorithm 2 for each of P. and returns their union. The size of the core-set clearly Σism k? < k2. Moreover, by Theorem 2.1 it is easy to verify that this is in fact composable core-set, because for any collection of colored point sets P(1), ,(N) one can treat them as having N different groups with k(²) < k; (more precisely, one can set k.6)) to be the number of points the optimal solution UJer pú) picks from p()).. Now note that although one does not know the value of k(") at the time of running Algorithm on p((), however since b(()) < k;, it is easy verify that running Algorithm 2 on p!()) with parameter k; as opposed to k.()) still works.
,(N),
Similarly,
get composable core-set for the SUM-NN DIST notion of diversity.
Corollary C.2. We have algorithm that given colored point set P = Uism P3 computes (not necessarily volor-abiding composable core-set of size (m k for the Fair Diversity Maximization problem under the SUM-NN DIST notion of diversity.
k; is super set of the core-set that would have been picked if the algorithm was run with parameter ()) opposed kg
Remark C.3 (Applications). Now that we showed how to get (not necessarily color-abiding) composable core-set, the result [20] readily implics that we have a streaming algorithm and an MPC algorithm for the Fair Diversity Maximization under the SUM-PAIRWISS DIST and SUM-NN DIST notions of diversity.
D Data Preparation and Additional Experiments
In order to demonstrate the effectiveness of the proposed approximation algorithms, we run sim- ulations on public and timed datasets. In this section, we give details on the used datasets, data preparation, pre-processing, and additional experiment results.
D.1 Datasets, data preparation, and experiments setup
Datasets and data preparation. We use Reddit public dataset [42] of text messages that are semantically embedded into metric space (e.g.. 748-dimensional metric space with BERT embed- dings [12]). We use this collection of Reddit messages as it provides the creation time stamp in the schema, which we need mark the relative recency of the messages, presented by its color
20

---

within a given month". We want to remark other commonly used Reddit datasets [37, 22]² are not considered in this work as they do not have the creation time in their schema. Since we have the messages metadata included in the creation timestamp 4 of a message i, we can assign a color color; of message as
& Emin
color; = [m
mmax
Emin
where émin and max are the minimum and maximum creation timestamp within the considered full input data and is the desired total number of colors. In this way, we have equidistant time intervals such that messages (relatively) close to one another by creation time belong to the same color and the most recent messages are in the m-th color. In this way, can also run Fair Diversity Maximization (FDM) for a desired distribution of number of messages within a color, i... k; for Vi 2, .... m, either by fairness (all k 's equal) or by recency (k; increases with i). In order to transform the message into a multi-dimensional space, we use BERT-model semantic embeddings [12] in our experiments (presented in the paper). Sentences and paragraphs embedding is an active area of NLP research [34, 36). Although, the quality of sentences and paragraphs semantic embedding out-of-scope for this work and we assume the messages are already given in the metric space, we have demonstrated (in Section D.2.4) the trend of the results is preserved by using other state-of-the-arr (such as MPNETv2 [35], T5 [29], RoBERTa [23] or MiniLM [38] and traditional (like GloVe [32]) pre-trained models for semantic embeddings. In the paper, the input "pool" of messages for the DM and FDM algorithms in the experiments is set to one month as we want to present to a user messages that are selected from timely and fresh period and the DM and FDM approximation algorithms make a decision for the most relevant, but also diverse and fairly distributed (per color) messages. We present results from January 2018 Reddit dataset that consists of 21, 21,474 samples, divided into four colors and our experiments show there a consistency in the results using input data from other periods.
We also utilize the MovieLens movie reviews dataset [18] from 2001, where the movie titles are semantically embedded into a metric space. In addition to the color determined by the creation time of the review (determined in the same way as explained for the Reddit dataset), for MovieLens dataset, we also assign a color based on the movie genre. There are 18 movie genres: ( ('Western', 'Documentary', 'Mystery', 'Film-Noir, 'Thriller', 'Crime', 'Adventure', 'Musical', 'Sci-Fi', 'War', 'Action', 'Fantasy,, 'Comedy', "Children's" s",, Aniimation, 'Horror', 'Romance', 'Drama'),
Description of the experiments. The main experiments we run in this work are the followings.
First we show that if we run DM on the data, the results are not balanced as we want, see Section 5 (main part, Figure 1) and Section D.2.1 (Figures 2 and 3), and thus we need to resort to FDM. Further, we show that using FDM the diversity does not decrease by much. This is shown in Section 5 (main part, Table 2) and Section D.2.2 (Tables 4 and 5).
Second, we show the effectiveness of the core-sets. We run our core-set construction algorithms (developed in Section and Section 4) on each color independently, to get a smaller size dataset. We then run the FDM optimization once on the union of the core-sets and once on the whole data. We measure the diversity loss and runtime improvement achieved by the use of core-sets. The results are given in Section 5 (main part, Table 3) and Section D.2.3 (Table 6).
The difference of the results (in the SUM-PAIRWISE notion of diversity) if we use alternative message embeddings are given in Section D.2.4 (Table 7).
Last, the practical comparison of our algorithm with the state-of-the-ar algorithm of Cecca- rello et al. [8] for core-set construction respect with to SUM-PAIRWIS PAIRWISE diversity is given in Section D.2.5 (Table 8).
"The messages in this dataset are given with a creation time (time stamp) and message IDs, but with no content message text and the message content is extracted by using the Reddit API: https://gtt reddit- archive/ archive/reddi weeeee/edi////eeeeeeeeeeeeeetttt tteditttwki/// /0Auth2. We request the messages for several months (using a similar script as the one used by the dataset creators) as we want to provide fresh messages from the recent month (our search pool) in our output.
com/
$ 'see also: fttps://wwg tensorflow. wwt.or//tttteeeeaaaaaaagggaeeeae https: http///gggggaac.eee///// co/ ///daaaett/eeeddt....aa. tifu 'Bssed on the quarter (roughly week) to which message belongs within this month.
and
21

---

D.2
Additional experiment results
D.2.1 Fairness the DM algorithms outcome and justification of FDM need
While the DM algorithms produce diverse results, they often do not have the balance the fairness prefer have. When make the color division based time periods (m 4, quarters within a month), DM algorithms produce imbalanced outcome (k: 20) for colors presence, see Figure (main part) and Figure? 2. The conclusions two-fold: (i) the most present messages recent ones and (ii) the results are also not equally balanced per quarter. In the case of Lns where the color is the movie genre (m 18 genres), the most present movies genres in the most optimal k 50 items are Drama and Comedy across all diversity distances and some genres are not present as shown in Figure 3. This highlights the need for the colored version of the algorithms (FDM) to achieve the desired fairness.
not the most
Nugbon of ('onggubl free roler
Numbur of codputt from mieer
Nunber Conlgnal from coler
1 S:to 10 au, it 2e-ie 24.3 I.
18 i7e
2:00 10 Jas 21.0 21
Lie Jua 2 20 10:0 24 las 2016 1. Ins Colors (time period
Colore (time period =
Colore time petiod in =))
(a) MovieLens (SUM- (AIN-PARRIIE)
MovieLens (SUM-NN)
(c) MovieLens
Figure 2: DM algorithm outcomes for all colors (m = 4) with equidistant time period as fairness colors in the MovieLens dataset (k: 20 items).
Ninber oampar from a odler
Nimber ond pata edee
Nimber fimmanea
18
12
Coomdoy
Chablrez's (geuree 18)
Ariin
Doae
Gazeda
Adhaa
Home
Coeab:
Draza
Actan
Caiddre's
Thilk
Colors
Colors
Coloce
(geuree 18)
(a) MovieLens
MovieLens (SUM-NN)
(c) MovicLens (MIN-PAIRWISE)
Figure 3: DM algorithm outcomes for top colors with genres fairness colors (m 18) in the MovieLens dataset (k: 50 items).
D.2.2 DM vs. FDM results
Reddit dataset. When we run FDM, we gain in fairness (or balancedness), but we lose diversity over the DM expressed in different metrics. How much the diversity becomes worse when we apply the FDM, for the Reddit dataset, is shown in Table Experiments show that we lose around 1% for SUM-PAIRWERS DIST; from few percent up no more than 20% for SUM-NN DIST and around 50% for MIN- PAIRWISE DIST (due to its fragility) for various distributions per color, while achieving desired per colors distribution, both in balancedness (uniform k; const) and recency (k; increasing linearly; km most recent items).
MovieLens dataset. The results for the MovieLens dataset follow the trend of the results of Reddit dataset, when we compare the diversity loss (and faireess gains). This is given in Table 4, comparable to Table 2 in the main part of the paper. on diversity, we lose less than 1 % for SUM- PAIRWISE DIST; few percents for SUM-NN DIST and around 50-70% for PIR-PIE DIST, while achieving the desired per color distribution. For this dataset, also experiments where the number of colors is larger (genres; = 18) and also
the cases with time as a color, experiments show that
22

---

see a similar trend of diversity loss of around 2-3% for for SUM-PAIRWISE DIST; few percents for SUM-NN DIST and around 50-55% for
DIST as shown in Table 5.
Table 4: The loss of diversity (% Div. loss) between DM vs. FDM on the full data, expressed as a relative change, of the concerned
SUM-NN and MIN-PAIRWISE distances for uniform (upper part) increasing (lower part) color values K; for MovieLens dataset with time period
within January 2001 as colors (m 4).
DM vs. FDM
SUM-PAIRWISE SUM-NN MIN-PAIRWISE
colors K;
Σ kg
% Div. loss
% Div. loss
% Div. loss
12,4.6
6
20
0.14%
1.46%
58.93%
3,
6,
9. 12
30
0.02%
3.33%
68. 68.94%
4,
12,
16
40
0.03%
1.62%
68.325
5.
10.
15,
20
50
0.02%
1.70%
67.64%
6,
12,
18,
24
60
0.02%
1.15%
67.36%
Table 5: The loss of diversity (% Div. loss) between DM vs. FDM on the full data, expressed as relative change, of the concerned SUM-PAIRWISE, SUM-NN and MIN-PAIRWTS, distances for uniform color values k; for MovieLens dataset with genres as colors (m 18).
DM vs. FDM
SUM-PAIRWISE SUM-NN
MIN-PAIRWER
colors K; Ek, % Div. loss
Div. loss % Div. loss
2, ........ 2]
36
2.84%
9.51%
52.63%
3, 3,
3
54
2.88%
5.78%
54.04%
4, 4,
72
2.87%
11.38%
53.09%
5. 5 ...
5
90
2.93%
12.52%
52.25%
18
D.2.3 Effectiveness of the core-sets results
Reddit dataset. We also run experiments to show the power of data summarization in terms of core-sets. The results in terms of diversity loss are on-par or with marginal difference if we apply the FDM to the union of core-sets, compared to FDM applied the full data. See Table for the results on both SUM-PAIRWTE and SUM-NN distances. (In the case of SUM-NN DIST, there are cases where one marginally better than the other?. .) Moreover, running FDM to the union of core-sets orders of magnitude faster compared to the same algorithm applied to the full data.
MovieLens dataset. As shown in Table 6, the comparison of the diversity outcome of the FDM applied on the full data versus the FDM applied on the data summary presented by the core-sets show similar trend as in the Reddit dataset (Table 3): few percent in diversity is lost for SUM-PAIRWI notion, while for the SUM-NN the results are mixed either in favor of the full data outcome or the core-set in terms of diversity. In the case of MIN- MIN-PAIRWISE the loss of diversity is either 0% in case the two points connected with the minimum distance are the union of the core-sets, or can be a higher value in the opposite case due to the fragility of the MIN-PA PAIRWISE DIST.
For example, FDM on the core-sets is occasionally better in diversity compared to the full data. One should note that the higher approximation factor contributes this.
23

---

Table The loss of diversity (% Div. loss) expressed as relative change diversity distances, and the running time gains (x times faster) of the FDM when applied to the union of core-sets compared to FDM applied to the full data for SUM- PAIR-PAR SUM-NN and MIN- MIN-PAIRWISE PAIRRWSISS distances for uniform or increasing color values kę for Movielen, dataset for January 2001 and m 4.
FDM full data vs. core-sets
SUM-PAIRWISE
SUM-NN
MIN-PAIRWISE
colors k;
Σ kg % Div. loss Time gain (x) % Div. loss Time gain (x) % Div. loss Time gain (x)
2, 2, 2
8
1.16%
1515.18
2.81%
225.64
0.00%
1 734.86
3, 3, 3,3
12
1.38%
967.96
-0.16%
604.15
26.51%
1 130.37
4,4,4,4
16
0.79%
617.67
-1.62%
325.73
46.17
874.17
5,5,5.5 6,6,6,6
20
0.61%
455.46
0.00%
207.71
26.75
686.42
24
0.62%
277.63
-0.23%
128.25
26.75
582.37
6,8
20
0.83%
412.02
2.94%
205.90
9.25%
515.18
3 12
30
0.77%
143.14
0.04%
83.48
0.68%
967.96
4, 12, 16
40
0.90%
121.84
5.30%
41.73
11.79%
617.67
5. 10,
15, 20
50
0.70%
30.68
0.05%
25.92
0.00%
455.46
6, 18,22
12,
60
0.75%
18.40
-8.55%
13.07
43.38%
277.63
D.2.4
Experiment results with alternative semantic embeddings
In this part, we show that using different embeddings for the messages produce similar trend in the obtained results. Table 7 present the comparison results in terms of diversity loss in the notion of SUM- PAIRWISE DIST we apply a FDM algorithm in comparison with the standard DM algorithm for various semantic message embeddings. The results show that have negligible loss of diversity, while we have the desired fairness (in terms of the requested k; s)) irrelevant of the employed pre-trained model to embed the messages in multi-dimensional space by using 6 state-of-the-ar pre-trained models for embedding a message or paragraph: BERT [12]; T5 [29]: MPNETv2 [35]; MiniLM [38]; RoBERTa [23] and GloVe [32]. We one of the highest performance and popular pre-trained models (without further training), however the quality of semantic sentence & paragraph embeddings using Large Language Models (LLM) out-of-scope for this work.
D.2.5 Comparison of core-set construction algorithms
In this section for the SUM-NN notion of diversity, we first compare the size of the obtained core-sets of the algorithm proposed this paper and the one from [8], in practice, for Reddit data. The results are given in Table 8. The results show that core-set size of the algorithm from [8] can indeed be very high providing very little summarization, while the core-set our proposal indeed much smaller (columns 3 and 4). As a result, our algorithm is few orders of magnitude faster than the core-set construction algorithm from [8] (column 5). This is while the diversity loss of our algorithm negligible (less than 1 % to few percent).
24

---

Table 7: The loss of diversity (% Div. loss) between DM vs. FDM on the full data, expressed as relative change, of the concerned SUM-PAIRWISE DIST for uniform increasing color values for six popular semantic embeddings. The results the main part of the paper and the other figures in
this appendix based on BERT [12] message embeddings.
DM vs. FDM
BERT [12]
T5 [29]
MPNETv2 [35]
colors &
Σ kg
%
Div. loss
% Div. loss
% Div. loss
2,2,
1.22%
1.15%
0.32%
3.3
12
0.98%
0.60%
0.32%
4,4,4,4
16
0.50%
0.30%
0.20%
5,5,5,5
20
0.47%
0.29%
0.11%
6,
24
0.19%
0.20%
0.05%
1,,4,688
20
0.42%
0.26%
0.08%
3, 6,9,
30
0.29%
0.23%
0.14%
4, 12,
40
0.25%
0.08%
0.06%
10, 15, 20
50
0.16%
0.10%
0.02%
6, 12, 18,24
60
0.12%
0.10%
0.03%
MiniLM [38]
RoBERTa [23]
GloVe [32]
%
Div. loss
% Div. loss
% Div. loss
2, 2,
8
1.14%
1.27%
1.11%
3,3,3,3
12
0.71% %
0.17%
0.47%
4,4,4,4
16
0.38%
0.06%
0.13%
5,5
20
0.32%
0.14%
0.03%
6,
24
0.21%
0.05%
0.10%
6,84
20
0.38%
0.31%
0.43%
3, 6,6,9 12
30
0.35%
0.18%
0.38%
4. 8, 12, 16
40
0.27%
0.19%
0.31%
5, 10, 15,
20
50
0.32%
0.14%
0.32%
6, 12,
18,24
60
0.33%
0.15%
0.13%
Table 8: The size of the union of core-sets produced by the algorithm of [8] and the size of the union of core-sets produced by our algorithm. The loss of diversity (% Div. loss) expressed as a relative change of diversity distances, and the running time gains (x times faster) of the FDM when applied to the union of core-sets produced by our algorithm vs. the one from [8] for SUM-PAIRWISE distance for uniform increasing color values for the Reddit dataset.
Corsets size comparison
U: core-sets size
core-sets compute
FDM (U: core-sets)
colors k.
Σ lb
[8] alg.
our alg.
Time gain (x)
% Div. loss
Time gain (x)
2, 2, 2,
12791
17.19
3.89%
1 055.62
3, 3, 3,
12
13486
56
9.20
0.62%
529.96
4, 4,4,4,4 4,4
16
13857
72
5.28
0.26%
458.05
5, 5, 5.
20
13993
154
3.65
1.69%
246.58
6, 6, 6,
24
14305
164
2.78
0.27%
129.73
25


Reviews:
[{"review_id": "oaSdkGM8oO", "reviewer": "Reviewer_CoyK", "summary": "This paper investigates data summarization problems.  Given a set of points in metric space, the goal is to select k points that are diverse. Diversity could be measured as the sum of squared distances, the sum of nearest neighbor distances, etc.\n\nConstant approximation algorithms for these problem are known.   This paper investigates core-sets for the problem.  A shortcoming of prior work is that say given two data sets that have been summarized, how can one combine their summarizations? Simply taking two solutions and combining them can give poor performance.   This paper offers coresets that are composable; that is, can be combined.\n\nThe core sets are of size poly(k), independent of n. The approximation ratio is constant for the sum of pairwise distances and is O(m log k) when there are m classes for the NN metric.  The ideas in the paper are simple natural approaches to the problem.\n\nA clear application of the core-sets is to get faster algorithms for big data sets.  Indeed, this approach naturally leads to much better run times practically.\n\nOverall, the paper is reasonable. On one hand, they theoretical ideas are simple. On the other, it seems to me that these results should be known and they clearly make the problem scalable to larger data sets.\n\nComment:\n\nThe paper would be even stronger by pointing out more applications of the coresets. They should have further applications in the design of distributed or streaming algorithms. ", "questions": "Have the authors thought of applying these ideas to MPC for parallel computing algorithms?  I think they should immediately lead to results in such settings. ", "limitations": "yes", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "The paper gives a new approach to a natural problem. Coresets construction should be known\n\nThey can achieve speed up practically using their ideas", "weaknesses": "The algorithmic and analysis ideas are simple", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank you for reviewing our paper.\n\nWe emphasize that our core-set results **do imply** streaming and distributed algorithms for the considered problem. As mentioned in our introduction [in the paragraph right before Section 1.1], the application of core-sets to streaming and distributed models is explained in detail in the reference [11] (IMMM, 2014).\n \nLet us describe how our core-set result implies an algorithm in the MPC model:\n\n- First suppose that the data of each group, i.e., $P_i$, is given to the $i$-th machine, each machine locally computes a core-set of small size (e.g. $O(k^2)$) on its own data and sends it to a single aggregator machine. The aggregator then runs some offline algorithm and computes the solution. Because of the composability property of the core-sets, the solution computed by the aggregator is a good approximation for the union of the whole data, i.e., P. \nThus, we get an MPC algorithm whose communication is only $O(k^2)$ per machine ($m k^2$ in total, where $m$ is the number of groups) and the algorithm runs in a single round. \n\n- Even if the partitioning of the input data is done arbitrarily as opposed to being based on the groups, a slight modification of the above gives an MPC algorithm. In particular, each machine now computes a core-set of size $mk^2$ as follows: For each of its subset of points from each group it computes a core-set of size $k^2$ and takes their union. Thus the overall communication of all machines is $Mmk^2$ (where M is the number of machines and $m$ is the number of groups). Again the algorithm runs in one round.\n\nWe will include this application to the MPC model in the paper."}, {"review_id": "1FgI0SSFZD", "reviewer": "Reviewer_S4pc", "summary": "This paper gives coresets for two different fair diversity measures (FDM). Fairness is defined as a partition matroid where the number of items from each part is fixed. The authors give a coreset for FDM under the sum-pairwise distance. They also give a coreset for sum-NN-distance. The proposed algorithms are compared against baselines for a real dataset. The main technique appears to be a based on the greedy k-center clustering (which the authors term as GMM). \n", "questions": "1. Why is the O(m log k) coreset guarantee useful?", "limitations": "The theoretical guarantees are not very impressive. ", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": " Coresets for these measures have not been studied, hence these are new results. Based on the experiments, the results are fairly practical. We get both a theoretical guarantee and a practical boost in performance.  \n\nIn the experiments, the authors compare with existing baselines to show that their coresets are much smaller while giving comparable performance.  While the technical contribution relies mostly on the k-center algorithm, I like the fact that the algorithms are simple.", "weaknesses": " The theoretical guarantee for the NN-distance diversity notion seems fairly weak, O(m log k). We already have an O(1) approximation guarantee algorithm anyway, so it is unclear why this is useful. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank you for reviewing our paper and for the kind words on the paper merit. \n\nWe want to clarify that the existing O(1) approximation is in the “standard offline setting” of the problem and it **does not** give a “core-set construction algorithm” (Please refer to Table 1). This is because those O(1) approximation algorithms assume to have access to the whole data at hand which is not the setting we consider. We will ensure to make this more clear in the final version of the paper. In our setting, each pointset corresponding to a group should be processed and summarized independently.\n\nMore precisely, the goal in the core-set setting is to find a “small summary” $T_i$ for each point set $P_i$ such that the union of the core-sets $T=\\bigcup_i T_i$ contains a good solution compared to the whole data $P=\\bigcup_i P_i$. Please refer to Definition 1.4 and Definition 1.1.\nWhile the goal of this paper is to present a good summarization algorithm for computing $T_i$ from $P_i$, the goal of existing O(1) approximation is for computing an approximate solution (on either $P$ or $T$).\n\nMoreover, in a practical scenario we have (e.g., news or social network feed), $k$ is in order of 10s (e.g, 20 or 50) and $m$ is often a single digit or in order of 10s in the worst case, thus the O($m \\log k$) can still be useful as also shown by our experiments."}, {"review_id": "54PSYOsxXl", "reviewer": "Reviewer_9Vmw", "summary": "A set of metric data points is comprised of m disjoint groups. The manuscript seeks for each group a subset of some given size such that the union of subsets the minimal pairwise distance (or sum of pairwise / nearest neighbour distances).  For constant factor approximation of minimising the sum of pairwise distances Section 2 of the manuscript reports a union of core-sets per group which for each group is quadratic in size. This result is achieved by applying Gonzalez's algorithm for each group and then simple post-processing steps over the obtained cluster centroids. Further results are achieved for sum of nearest neighbour distances as a diversity measure.", "questions": "Q1) How exactly does the fairness constraint relate to the core-set / \"solution\" sizes and how can the core-sets be larger than the group sizes specified in the fairness constraints? (see W1)", "limitations": "Relevant limitations seem to be discussed.", "rating": 6, "confidence": 1, "soundness": 3, "presentation": 1, "contribution": 3, "strengths": "S1) Challenging and natural problem: fairness constraint akin to stratified sampling to achieve good group representation and diversity constraint to achieve good overall representation\n\nS2) Non-trivial analysis: size of core-sets for min-pair-sum independent of the data size and distribution unlike in prior work.\n\nS3) Practical: analysed methods are simple and sufficiently efficient for practical purposes\n\nS4) Presentation is for the most part clear and prior work seems to be thoroughly discussed and compared against.", "weaknesses": "W1) Presentation could be clearer in some key points\n\nFairness constraint is not fully clear. The empirical results seem to indicate that the sizes per group dictate the sizes of the core-sets, but other parts of the paper indicate that the size of the core-sets could be larger than the dictated group sizes. Are the core-set sizes meant to be the intermediate sizes before the post-processing step?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank you for your review and positive feedback.\n\nPrecisely as you say, the goal in our paper is to provide an intermediate summary (i.e., a core-set) such that the union of the core-sets contains a good solution relative to the whole data. Later on, as a post-processing, one can use any exact or approximation algorithm on the union of the computed summaries to get a final solution. This is what we do in our experiments too.\n\nPlease refer to Definition 1.4 and Definition 1.1 for exact definition of our setting. In particular we provide an algorithm which given a point set $P_i$, it computes a core-set $T_i$. The size of the core-set $T_i$ should be **low but not necessarily $k_i$**. We want our summaries to have the property that\n\n$div_{k_1,...,k_m}(T) \\geq div_{k_1,...,k_m}(P)$\n\nThis means that the union of the core-sets, i.e., $T=\\bigcup_i T_i$ should contain at least $k_i$ points from color $i$ such that their overall diversity is relatively large in comparison to the optimal set of points one could have picked out of the whole data, i.e., $P$.\n\nWe will add more explanation to clarify this distinction right after formal Definitions 1.1 and 1.4 in the final version.\n\nDear reviewer 9Vmw, thanks again for the comments that improve the manuscript. Considering you stated the presentation is clear in most of the parts (S4) and with the newer clarifications that we will add around key concepts, would it be possible to reconsider your score for a higher (and the presentation score)?\n"}, {"review_id": "36Aovo7oQP", "reviewer": "Reviewer_aN6A", "summary": "The study presents improved core-set construction algorithms for maximizing diversity under partition constraints.\nTwo diversity measures were considered: sum-of-pairwise distances and sum-of-nearest-neighbor distances.\nThe algorithms are validated through real-world application to time-sensitive message data, resulting in a 100x speedup and minor diversity loss while improving space usage in streaming settings.", "questions": "Section 1.3 defines the problem as selecting subsets S_i of k_i points from P_i to maximize div(S). However, the subsets S_i don't strictly contain k_i points in your final results. Instead, they include the core-set and the closest k_i points to each seed, effectively increasing the core-set size to k_i^2, as observed in the 'Core-set for SUM-PAIRWISE DIST' case. Could you please clarify how these results align with your original problem definition? Furthermore, could you please provide additional detail in your problem definition to help readers understand how the algorithm's results can serve as a potential solution to the problem?", "limitations": "The authors adequately addressed the limitations. There are no potential negative societal impacts from their work.", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "Algorithms 2, 3, and 4, despite their relative simplicity, provide significant insights, primarily stemming from the proofs of approximations related to their definitions.\nThese algorithms' straightforward yet effective design and the resultant analytical insights shed new light on the problem. These aspects, therefore, make these algorithms especially appealing to a broad research community. Conference attendees will find these insights valuable, sparking potential discussions around their contributions and their implications in the field.", "weaknesses": "While the paper offers some contributions, its structure requires revision for improved clarity, particularly moving the detailed 'Overview of the Algorithms' from the first section to the respective sessions dealing with the algorithms and balancing the disproportionate length of the first section within the overall context.\n\nThe renaming of 'Diversity Maximization under Partition Constraints' to 'Fair Diversity Maximization' is somewhat perplexing. The 'fairness constraints' applied in this study do not differ significantly from the 'partition constraints' defined in the existing literature. Moreover, in other works (e.g., [22]), the term' fairness' is applied based on specific definitions like group fairness or statistical parity. The decision to redefine 'partition constraints' as' fairness constraints' without a clear distinction is somewhat confusing, making it more difficult to discern the precise contributions of this paper.\nStill, regarding the use of \"fairness constraints\" throughout the paper, the paper presents two main experiments. The first involves grouping a dataset of messages by creation time to compute a diverse summary that favors recently over older messages. The second uses the method to control each genre's contribution to a movie recommendation system. However, neither of these experiments demonstrates the necessity of applying fairness constraints (as defined in the literature) to solve the proposed problem.\n\nThe GMM Algorithm, a fundamental building block of the method, must be correctly defined. Since it initially selects some arbitrary point as the first element of S, [11]'s definition is accurate. In fact, because S begins as an empty set, the execution of line 3 in the authors' definition is inconsistent.\n\nThe text contains some English usage errors that affect clarity. Specifically, the phrase \"based on greedy\" found in line 107 could benefit from a more explicit definition. The part containing \"along the way\" in line 101 is vague and could be replaced with a more descriptive phrase. Furthermore, key terminologies, such as the \"aspect ratio\" of the dataset mentioned in lines 9, 86, and 94, are misused or not sufficiently defined.\n\nSome details of the experiments in the main text, such as the choice of 21,474 samples mentioned in line 294, appear arbitrary, and the rationale for their selection is buried in the appendix.\nFinally, the paper would greatly benefit from maintaining consistent naming and notation across all sections, enhancing its comprehensibility and overall cohesiveness.\nFor example, the \"div\" definition in line 231 should use the same notation as in line 238; many references to core-set vs. coreset.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your positive feedback mentioning that our paper provides significant insights, effective algorithms, sound theoretical results supported by experiments, and, indeed, it can be of broader interest of the NeurIPS community and the conference attendees. Also thank you for all the feedback to improve the presentation of the paper. In what follows we address your comments in more detail.\n\n\n> Regarding the organization of Section 1 and having “overview of the algorithms” subsection\n\nThank you for your suggestion on distributing the “overview of the algorithms” over to the corresponding sections. We believe this is more of a style of writing (e.g., this is very common in the theory community) . We are happy to follow your suggestion and will move the content of the section “overview of the algorithms” to the corresponding sections to balance the length of different sections.\n\n> Regarding your comment on the notions of “fairness constraint” vs. “partition constraint”\n\nBoth notions are common in the literature. In fact [22] and [23] use “Diverse Data Selection under Fairness Constraints” to refer to the exact same problem of FDM under the minimum pairwise distance notion of diversity. We use the same grouping constraint as they do.\n\nAlthough we use “fairness constraint” similar to [22] and [23], we are explicitly referring to the term “partition constraint” as early as the second paragraph in the introduction. Again we are happy to rename all instances of “fairness constraint” to “partition constraint” per your suggestion.\n\n> Regarding your comment on the initialization of the greedy (GMM) Algorithm 1\n\nThanks, we fixed this. Please check the PDF one-pager attached.\n\n> Regarding your minor comments on putting more details on dataset size in the main body, typos, and language issues:\n\nThank you, we will also add more explanation around the datasets from the appendix to the main body (done this way due to space constraints). We will address the language issues that you mentioned and fix the typos with respect to “div”, and be consistent using “core-set” term. We will correct the the terms “based on greedy” and “along the way”. We will also define the aspect ratio clearly in the final version.\n\n> Regarding your comment / question on the definition of core-sets.\n\n**Definition 1.1** is the definition of diversity maximization under fairness/partition constraint. Here, the goal is to compute an **approximate solution** $S_i\\subset P_i$ such that\n \n1) $\\|S_i\\|$ is exactly $k_i$.\n2) The overall diversity of $\\bigcup_i S_i$ which consists of exactly $k=\\sum_i k_i$ points is maximized.\n\n**Definition 1.4** on the other hand which is the focus of this paper defines **composable core-sets** for FDM. The goal here is to summarize each $P_i$ independently and get a core-set $T_i \\subset P_i$ such that\n\n1) Size of the core-set i.e., $\\|T_i \\|$ is small.\n2) The union of the core-sets $T=\\bigcup_i T_i$ contains a good solution.\n\nOnce we have a good core-set construction algorithm, one can run any exact or approximate algorithm on the union of the core-sets/summaries as post-processing and compute the final solution on (e.g. one can use the algorithm of [24] referring to Table 1) on $T$.\n\nWe will expand these definitions and put more details on them in the revision.\n\n\n>Although the findings from the study may be of interest to conference attendees, the issues identified indicate that the manuscript is not ready for publication in its current form. Hence, my recommendation is a borderline rejection of this manuscript. This manuscript does not meet the necessary standards for publication and requires substantial revisions\n\nDear reviewer aN6A, once again we sincerely thank you for pointing us to places for improving the manuscript. While we agree with all your comments, we believe all of them are easily addressable and not a strong basis for “borderline reject”. We will further check the paper’s readability and structure. \n\nCould you please consider increasing your score given that we addressed all the above concerns and will apply the corresponding changes to the final draft? "}]

Author rebuttal:
We sincerely thank all four reviewers for the positive feedback and their valuable comments. We provided a response individually to all the reviewers. Please let us know if there are additional questions that we can address during the discussion phase.

Meta-review: Overall, reviewers were positive about the paper. The model for data summarization is natural. The main shortcoming is that the techniques are not particularly deep. Still, the results will likely be of interest.
Decision: Accept (poster)