Optimization of Inter-group criteria for clustering with minimum size constraints
Authors: Eduardo Sany Laber
Lucas Murtinho
Venue: NeurIPS 2023 poster (2023)
Keywords: Single Link
clustering
approximation algorithms
complexity
inter-group criterion
TL;DR: We present algorithms for two natural intra-clustering criteria that work well on constrained cases in which all groups must have a minimum number of elements.

Abstract: Internal measures that are used to assess the quality of a clustering usually take into account intra-group and/or inter-group criteria.
There are many papers in the literature that propose algorithms with provable approximation guarantees for optimizing the former. However,  the optimization of inter-group criteria is much less understood.

Here, we contribute to the state-of-the-art of this literature by devising algorithms with provable guarantees for the maximization of two natural inter-group criteria, namely the minimum spacing and the minimum spanning tree spacing. The former is the minimum distance between points in different groups while the latter captures separability through the cost of the minimum spanning tree that connects all groups. We obtain results for both the unrestricted case, in which no constraint on the clusters is imposed, and for the constrained case where each group is required to have a minimum number of points. Our constraint is motivated by the fact that the popular Single-Linkage, which optimizes both criteria in the unrestricted case, produces clustering with many tiny groups.

To complement our work, we present an empirical study with 10 real datasets that provides evidence that our methods work very well in practical settings.

Optimization of Inter-group Criteria for Clustering with Minimum Size Constraints
Eduardo S. Laber Department of Computer Science PUC-Rio
Lucas Murtinho Department of Computer Science PUC-Rio
Rio de Janeiro, RJ Brazil laber@inf puc-rio.
Rio de Janeiro, RJ - Brazil
Imurtinho@aluno. puc-rio.br
Abstract
Internal measures that are used to assess the quality clustering usually take into account intra-group and/or inter-group criteria. There are many papers in the literature that propose algorithms with provable approximation guarantees for optimizing the former. However, the optimization of inter-group criteria is much less understood.
Here, we contribute to the state-of-the-an of this literature by devising algorithms with provable guarantees for the maximization of two natural inter-group criteria, namely the minimum spacing and the minimum spanning tree spacing. The former is the minimum distance between points in different groups while the latter captures separability through the cost of the minimum spanning tree that connects all groups. We obtain results for both the unrestricted case, which no constraint on the clusters is imposed, and for the constrained case where each group is required to have minimum number of points. Our constraint is motivated by the fact that the popular Engle-linkage which optimizes both criteria in the unrestricted case, produces clusterings with many tiny groups
To complement our work, we present an empirical study with 10 real datasets, providing evidence that methods work very well in practical settings.
Introduction
Data clustering is a fundamental tool in machine learning that is commonly used in exploratory anal- ysis and reduce the computational resources required handle large datasets. For comprehensive descriptions of different clustering methods and their applications, we refer to Jain et al. (1999); Hennig al. 2015). In general, clustering is the problem partitioning set of items so that similar items are grouped together and dissimilar items are separated. Internal measures that are used to assess the quality of a clustering (e.g. Silhouette coefficient Roussceuw (1987) and Davies-Boulle Bouldin index Davies & Bouldin (1979) usually take into account intra-group and inter-group criteria. The former considers the cohesion of a group while the latter measures how separated the groups are.
coefficien(Rouusseeuuy
There are many papers in the literature that propose algorithms with provable approximation guar- antees for optimizing intra-group criteria. Algorithms for k-center, k-medians and k-means cost functions Gonzalez (985); Charikar et al. (2002); Ahmadian et al. (2020) are some examples. However, optimizing inter-group criteria is much less understood. Here, we contribute to the state- of-the-art by considering the maximization of two natural inter-groe criteria, namely the minimum spacing and the minimum spanning tree spacing.
Our Results. The spacing between two groups of points, formalized in Section 2 is the minimum distance between point in the first and point in the second group. We consider two criteria for
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

capturing the inter- group distance of clustering, the minimum spacing (Min-Sp) and minimum spanning tree spacing (MST-Sp). The former is given by the spacing the two groups with the smallest spacing in the clustering. The latter, as the name suggests, measures the separability of clustering according to the cost of the minimum spanning tree (MST) that connects its groups; the largest the cost, the most separated the clustering is.
We first show that single- lin-agen a procedure for building hierarchical clustering, produces clustering that maximizes the MST spacing. This result contributes to better understanding of this very popular algorithm since the only provable guarantee that we are aware of (in terms of optimizing some natural cost function) is that it maximizes the minimum spacing of a clustering Kleinberg & Tardos [Chap 4.7]. Our guarantee [Theorem [.3] is stronger than the existing one in the sense that any clustering that maximizes the MST spacing also maximizes the minimum spacing. Figure shows an example where the minimum spacing criterion does not characterize well the behavior of single-linkage
Despite its nice properties, single-linkage tends to build clusterings with very small groups, which may be undesirable in practice. This can be seen in our experiments (see Figure 2 and is related the well-documented fact that single-linkage suffers from the chaining effect (Jain et al. 1999)[happ 3.2].
To mitigate this problem consider the optimization of the aforementioned criteria under size constraints. Let L be a given positive integer that determines the minimum size that every group in a clustering should have. A (k, T.) clusttrtgi is clustering with & groups in which the smallest group has at least elements. For the Min-Sp criterion we devise an algorithm that builds clustering with at least T.(1- <) points per group while guaranteeing that its minimum spacing is not smaller than that of an optimal (k, -lluuttrrin This result is the best possible in the sense that, unless P == NP, it is not possible obtain an approximation with subpolynomial factor for the case in which the clustering is required to satisfy the hard constraint of L points per group. For the MST-Sp criterion we also devise algorithm with provable guarantees. produces clustering whose MST-Sp is most log k factor from the optimal one and whose groups have each at least pL(1 c)/2 points, where p is a number in the interval [1, 2] that depends on the ratio n n/kL. We also prove that the maximization of this criterion is APX-Hard for any fixed k.
$ #
Figure 1: Partitions with 3 groups (defined by colors) that maximize the minimum spacing. The rightmost one is built by single-linkage, but both of them maximize the minimum spacing showing that this condition alone is insufficient to properly characterize single-linken
behavior.
We complement our investigation with an experimental study where we compare the behaviour of the clustering produced by our proposed algorithms with those produced by k-means and single-linkage for 10 real datasets. Our algorithms, as expected, present better results than k-means for the criteria under consideration while avoiding the issue of small groups observed for single-linkage.
Related Work. We only aware of few works that propose clustering algorithms with provable guarantees for optimizing separability (inter-group) criteria. We explain some of them.
The maximum k-cut problem is widely studied problem in the combinatorial optimization commu- nity and its solution can be naturally viewed as a clustering that optimizes separability criterion. Given an edge-weighted graph G and an integer k 2 2, the maximum k-cut problem consists of finding a k-cut (partition of the vertices the graph into à groups) with maximum weight, where the weight of a cut is given by the sum of the weights of the edges that have vertices in different groups of the cut. The weight of the k-cut can seen as separability criterion, where the distance between two groups is given by the sum of the pairwise distances of its points. It is well-known that random

---

assignment of the vertices (points) yields an (1 - 1/k) approximation algorithm. This bound can be slightly improved using comi-definttive programming Frieze & Jerrum (1997).
The minimum spacing, one of the criteria we studied here, also admits an algorithm with provable guarantees. In fact, we already mentioned, it can be maximized in polynomial time via the Single-linkag algorithm Kleinberg & Tardos (Chp 4.7]. In what follows, we discuss works that study this algorithm as well as works that study problems and/or methods related to it.
single-link has been the subject of a number of researches (Zahn 1977 Kleinberg 2002
Carlsson & Mémoli, 2010; HHfmmyr 2020). Kleinberg (2002) presents axiomatic study of clustering, the main result of which is a proof that it is not possible to define clustering functions that simultancously satisfy three desirable properties introduced in the paper. However, it shown that by choosing a proper stopping rule for the single-1 mange-linkage it satisfies any two of the three properties. [Carlsson& & Mémoli (010) replaces the property of Kleinbbr (2002) that the clustering function must output partition with the property that it must generate a tree (dendogram). Then, was established that single-linne linnage satisfies the new set of properties. In more recent work, Hofmeyr (2020) establishes a connection between minimum spacing and spectral clustering, While the aforementioned works prove that Lnngl-linkage has important properties, in practice, is reported that sometimes it presents poor performance due to the so-called chaining effect (Jain et al. (1999) [Chap 3.2
single-linkage belongs to the family of algorithms that are used to build Hierarchical Agglomer- ative Clustering (HAC). Dasgupta (216) frames the problem of building a hierarchical clustering as a combinatorial optimization problem, where the goal is to output a hierarchy/tree that minimizes a given cost function. The paper proposes cost function that has desirable properties and an algorithm to optimize it. This result was improved and extended by series of papers (Roy & Pokutta 2016 Charikar & Chatziafratis, 2017; Cohen-Addad et al., 2019). The algorithms discussed in these papers do not seem to be employed in practice. Recently, there has been some effort to analyse
HAC algorithms that are popular in practice, such as the Average Link (Moseley & Wang 2017
Cohen-Addad et al. 2019. Our investigation of single- mogll-linkage linkage can be naturally connected with this line of research.
Finally, in a recent work, Ahmadi et al. (0022) studied the notion of individual preference stability (IP-stability) in which a point is IP-stable if is closer to its group (on average) than to any other group (on average). The clustering produced by s single-linkage
presents a kind of individual preference stability in the sense that each point is closer to some point in its group than any point in some other group.
Potential Applications. We discuss two cases in which the maximization of inter-group criteria via our algorithms may be relevant: ensuring data diversity when training machine learning algorithms and population diversity in candidate solutions for genetic algorithms.
When training machine learning model, ensuring data diversity may be crucial for achieving good results (Gong et al., 2019). In situations in which all available data cannot be used for training (e.g. training in the cloud with budget constraints), it is important to have a method for selecting a diverse subset of the data, and our algorithms can be used for this: to select = kL elements, one can partition the full data set into k clusters, all of them containing at least L members, and then select elements from each cluster. Using single-linken
to create kL groups and then picking up one element per group is also a possibility but would increase the probability of an overrrepresentation of outliers in the obtained subset, these outliers would likely be clustered singletons (see Figure 2 in Section 5)
Note that our algorithms can be used to create not only one but several diverse and disjoint subsets, which might be relevant to generate partitions for cross-validation or for evaluating a model's robustness. For that, each subset is obtained by picking exactly one point per group.
For genetic algorithms, maintaining diversity over the iterations is important to ensure a good explo- ration of the search space (Gupta & Ghafir (012). If all candidate solutions become too similar, the algorithm will become too dependent on mutations for improvement, as the offspring of two solutions will likely be similar to its two parents; and mutation alone may not be enough to fully explore the search space. We can apply our algorithms in a similar manner as mentioned above. by partitioning, at each iteration, the solutions into & clusters of minimum size L and selecting the best L solutions from each cluster, according the objective function of the underlying optimization problem, to maintain
3

---

the solution population simultaneously optimized and diverse. Using single-linken could lead several poor solutions being selected to remain in the population, case they are clustered as singletons.
We finally note that algorithm that optimizes intra-group measures (e.g. k-means k-medians) would not necessarily guarantee diversity for the aforementioned applications, as points from different groups can be close each other.
2 Preliminaries
Let X be a set of n points and let dist X x X' + R+ be a distance function that maps every pair of points in X' into a non-negative real.
Given a k-clustering C (C....., Ct), we define the spacing between two distinct groups C; and Cj of C as
spacing(Ci,, Cj) min (dist(x,y)) =EC.NEC
Then, the minimum spacing of C' is given by
Min-Sp(C) == min (spacing(G.C)) C,C,)) d, 443
A k-clustering C induces on (X, dist) edge-weighted complete graph Ge whose vertices are groups of and the weight w(eig) the edge eij between groups C; and C given by w(esz) spacing(C,, C₁). For a set of edges S Ge we define w(S) := Eees w(e).
The minimum spanning tree spacing of C (MST-Sp(C)) is defined as the sum of the weights of the edges of the minimum spanning tree (MST(Ge)) for Gc. In formulae,
MST-Sp(C) ;=
E
w(e).
eEMST(GE)
Here, we will be interested in the problems of finding partitions with maximum Min-Sp and maximum MST-Sp both in the unrestricted case in which no constraint on the groups is imposed and in the constrained case where each group is required to have at least T. points.
Single-Linkage. We briefly explain single- eesile-linkeee linkage. The algorithm starts with groups, each of them consisting of point in X. Then, at each iteration, it merges the two groups with minimum spacing into new group. Thus, by the end of the iteration i it obtains clustering with & groups. In Kleinberg & Tardos 2006) it is proved that the single-linkage obtains a k-clustering with maximum minimum spacing.
Theorem 2.1 (Kleinberg & Tardos 2006), chap 4.7). The single- algorithm obtains the k-clustering with maximum Min-Sp for instance dist).
single- -inkage and minimum spanning trees are closely related since the former can be seen as the Kruskal's ' algorithm for building MST's with an early stopping rule. To analyze our algorithms we make use of well-known properties of MST's as the cut property [Kleinberg & Tardos (2006), Property 4.1 and the cycle property Kleinberg & Tardos (2006), Property 4.20]. Their statements can be found in the appendix.
For ease of presentation, we assume that all values of dist are distinct. We note, however, that our results hold if this assumption is dropped.
3 Relating Min-Sp and MST-Sp criteria
We show that single-linkage finds the clustering with maximum MST-Sp and the maximization of MST-Sp implies the maximization of Min-Sp. These results consequence of Lemma[3.]tha generalizes the result of Theorem 2.1 The proof of this lemma can be found in the appendix.
Fix an instance / single-linken for instance and Tsr. MST for GesL- Moreover, wiLh the weight of the i-th smallest weight of Tst.
(X, dist, "ist,k) k). In what follows, CSt. is a k-clustering obtained by

---

Lemma 3.1. Let C be a k-clustering for I and let wi be the weight of the i-th smallest weight in MST T for the graph Gç. Then, w.t 2 w.
Theorem 3.2. The clustering CST. returned by single-linkage for instance (X, dist, k) maxi- mizes the MS criterion.
Proof. Let C be keclusteringg for (X, dist, k) and let w; be the weight of the i-th cheapest edge of the MST for Ge. Since wiSh 2 w; for i 1,.... ......,.... k- 1, we have that
MST-SP(CsL)
SL W
wi
MST-Sp(C)
Theorem 3.3. Let C be clustering that maximizes the MST-Sp criterion for instance (X, dist, k). Then, it also maximizes Min-Sp for this same instance.
Proof. Let assume that C* maximizes the MST-Sp criterion but it does maximize the Min-Sp criterion. Thus, wft > wi. where wi is the minimum spacing of C*. It follows from the previous lemma that
k-1
k-1 ii
MST-Sp(CsLL) = Σ
SL
MST-Sp(C*),
i=1
which contradicts the assumption that C* maximizes the MST-Sp criterion.
The next example (in the spirit of Figure shows that partition that maximizes the Min-Sp criterion may have a poor result in terms of the MST-Sp criterion.
Example 3.4. Let be positive number much larger than Moreover, let [t] be the set of the t first positive integers and S = {(D i,j)li,j E - 1]} (D.k) be set of (k 1)2 + points in R
Lingle-linken builds a k-clustering with Min-Sp / and MST + (k- 2 S. However, the k-clustering (CI..... Ck), where Cj {(D i,,)) l...., k 1.. for k and C = ((D,k)) has Min-Sp and MST-Sp- (k: 1),
Avoiding small groups
In this section, we optimize our criteria under the constraint that all groups must have at least points, where L is positive integer not larger than n/k that is provided by the user. Note that the problem is not feasible if n/k.
We say that an algorithm has (B, aapproiappooiiaaionn for criterion x E (Min-Sp, MST-Sp} if for all instances it obtains a clustering C₁ such that Cj (k. |elustceut and the value of k for Cj is at least 7 OPT, where OPT's is the maximum possible value of к that can be achieved for (k., cllustrrin
We first show how to obtain a (1 c, 1) for the Min-Sp criterion.
4.1 The Min-Sp criterion
We start with the polynomial-time approximation scheme for the Min-Sp criterion. Our method uses, as subroutine, an algorithm for the max-min scheduling problem with identical machines Csirik et al. (1992); : Woeginger (1997). Given machines and set of n. jobs, with processing times Pı.... Pa. the problem consists finding an assignment of jobs to the machines so that the load of the machine with minimum load is maximized. This problem admits polynomial-timg approximation scheme Woeginger (1997).
k, e) be routine that implements this scheme. It receives as input parameter 6 > 0, an integer i and a list of numbers P (corresponding to processing times). Then, returns partition of P into & lists (corresponding to machines) such that the sum of the numbers of the list
Let MaxMinSchedi
5

---

with minimum sum is at least (1 - <)OPT, where OPT is the minimum load of a machine in an optimal solution of for the max min scheduling when the list of processing times is P and the number of machines is k.
Algorithm 1 as proved in the theorem, obtains a (k, [(1 <) )-llsteriig whose Min-Sp is at least the Min-Sp of an optimal (k, -.llusteriing For that, it looks for the largest integer t for which the clustering Ar obtained by executing steps of single-linken resulting groups into & groups (via MaxMinSched) is a (k, L(1 -cllcuuser We assume that MaxMinSched, in addition of returning the partition of the sizes, also returns the group associated to each size.
and then combining the
Algorithm AlgoMinSp(d'; dist; k; E > 0;L)
+ n k
while 2 0 do
Run & merging steps the single-linken for input
Let C,...., - the groups obtained by the end of the / steps
P (IC
A f- MaxMinSched(P,
if the smallest group A, has size greater than or equal to L(1 - c) then Return A,
else -
Theorem 4.1. Fix E >> O. The clustering A₁ returned by the Algorithm iis (k, (1- -1-=ce)r-uustrring that satisfies Min (fin) 2 Min-Sp(C*) where C* is the (ks -llsssterinng with maximum Min-Sp
Proof. By design, A, has k groups with at least L(1 c) points in each of them.
For the sake of contradiction, let assume that Min-Sp(AA) < Min-Sp(C").
Let C (Ct...., Cn-4) be the list of n t groups obtained when merging steps of s single-linkage are performed. We assume w.l.o.g. that C1 and C2 are the two groups with minimum spacing in this list, so that Min-Sp(C) spacing(CI, C2). Since As is a k-clustering that is obtained by merging groups in C we have Min-Sp(AA) 2 Min-Sp(C) = spacing(C1, C2).
For = 1,.... Min-Sp(C*). ). In addition, we must have C₁ UC2 S C for some e C*, otherwise, again, we would have Min-Sp Min-Sp((A.) Min-Sp(C*).
we have that C C C for some C' E C*, otherwise we would have Min-Sp(A.) >
We can conclude that there is feasible solution with minimum load not smaller than for the max-min scheduling problem with processing times P' = ((C1 U followed by MaxMinSched k. c).
(C--() and K
machines. Thus, by running + steps of sangle-linken we would get a k-clustering whose smallest group has least L(I e) points. This implies that the algorithm would have stopped after performing + merging steps, which is contradiction.
Algorithm as presented, may run Fortunately, it admits an implementation that runs single- -inkaee just once, and performs an inexpensive binary search to find suitable I.
- k times, which may be quite expensive.
The next theorem shows that Algorithm Tass essentially tight guarantees under the hypothesis that P # NP. The proof can be found in the appendix
Theorem 4.2. Unless P = N. for any a = poly(n)), the problem of finding the (k, -)-clustering that maximizes the Min-Sp criterion does admit (1, appproximmain
4.2 The MST-Sp criterion
Now, we turn to the MST-Sp criterion. Let p min n/k .2.. Our main contribution is Algorithm 2
obtains (م(ا_c) Tr ;) approximation for this criterion, where Hx-1 = >k-1 is the (k- 1)
Harmonic number. Note that H:-1 is O(log k).

---

In high level, for each & = ....,,,, k. the algorithm calls AlgoMinSp (Algorithm I to build clustering Ag with groups and then transforms A (lines 5-13) clustering A, with & groups. In the end, it returns the clustering, among the k considered, with maximum MST-Sp.
Algorithm 2 Constrrainnd-KaxxsStttt dist; k; e)
1: for f = .,.... k do
2: A f AlggoMinSp(R,dist.....
3: NonVisited A
4: Ar -
5: for each A' in A/e iterating from the largest group the smallest do
6: NonVisited + NonVisited A'
2/44
7:
Split + p(1-c)
8:
| NonVisited SplitNumber < k then
9:
Split A' into Split Numitr as balanced as possible groups and add them to A
10:
else
11:
Split A' into & - |Ad NonVisited as balanced possible groups; add them A₂ Add all groups in NonVisited to Ae
12:
13: Break
14:
Return the clustering A,, among the obtained, that has the maximum MST-Sp
We remark that do not need to scan the groups in A', by non-increasing order of their sizes to establish our guarantees presented below. However, this rule tends to avoid groups with sizes smaller than L.
Lemma 4.3. Fix E > 0. Thus, for each every group in Ag has at least
p(1-0)L
points.
2
Proof. The groups that added A in line 12 have at least (1 L) points while the number of points those that are added at either line or 9 is at least
LA'
p(l - E)
A21a1/((1
c)
2
Moreover, if the For is not interrupted by the Break command, the total number of groups in A is
Σ 2| p( C)
Σ
p(1 c)L - -
2|A'
2n
k
2k
k 222 k.
p(1 C)L
(1
A'E.A;
A'EAY
Since the For is interrupted as soon A groups can be obtained then, Ar has A groups.
For the next results, denote the cost of the i-th cheapest edge in the MST for Gc-. Our first lemma can be seen as generalization of Theorem 4.1 Its proof can be found in the appendix.
C* denote the (k, cllclustering with maximum MST-Sp and wy to
Lemma 4.4. For each f, Min-Sp(A') w6-e+1
simple consequence of the previous lemma is that the MST-Sp of clustering A, is least (e w The next lemma shows that this bound also holds for the clustering Aç. The proof consists of showing that each edge of a MST for A'e is also an edge of a MST for As-
Lemma 4.5. For each & = 2.... we have MST-Sp/AA) 7 (E 1) wh-4+1
Proof. Let T3 and TV be, respectively, the MST for G,,, and G By the previous lemma, each of the (E- - 1) edges of TV has at least Min-Sp(AA,) > Wi-441 -41 Thus, establish the result, is enough to argue that each edge of TV also belongs Tr.
say that group A Ar generated from group A' A₁ A = A' or is one of the balanced groups that is generated when A' is split in the internal For of Algorithm We say that
7

---

vertex r in GA, is generated from a vertex x' in Gay if the group corresponding to is generated by the corresponding to _'.
Let e' =''u' be edge in T and let S' be cut in graph GA,, whose vertices are those from the connected component T \ e' that includes u'. We define the cut S of GAe as follows S = {i E GA, |æ is generated from some x' E {").
Let and be vertices generated from u' and v', respectively, that satisfy w(wr) w(('v") It is enough to show that wy is the cheapest edge that crosses 5 since by the cut property (Kleinberg & Tardos (2006), Property 4.17.] this implies that E Tç. We prove it by contradiction. Let us assume that there is another edge f yz that crosses S and has weight smaller than w(wv). Let y/ and z' be vertices in GAs that generate y and 2, respectively, and let f s/z'. Thus, w(f") S w(f) w(wv) w(w'v) (') w(e'). However, this contradicts the cycle property of MST's Kleiiberg & Tardos (2006), Property 4.20] because it implies that the edge with the largest weight in cycle of Ar comprised by edge f' and the path in T the connects y' to z' belongs to the Ty
The next theorem is the main result of this section.
Theorem 4.6. Fix > O. Algorithm 2 is [- the (ke L) cluustring that maximizes the MST-Sp criterion.
Hh H
approxxaattn for the problem of finding
Proof. Let C be the clustering returned by Algorithm (k, [1-9pp J-clustering
Lemma
4.3
guarantees that C is
Thus, we just need argue about MST-Sp(C).. We have that
MST-Sp(C*) = Σ u W6-1+11
and, due to Lemma 4.5 MST-Sp(C) 2 max{(e - 1) W s
Let i be the value that maximizes (f-1)- It follows that w S ((f-1)/i-1))ee for i .....,k. k. Thus,
MST-Sp(C*) E whiil MST-Sp(C)
(L-1) 1) w "-i41 Ei=2
Ha-1
(e - 1) w x-i11
(f- w0 k-1+1
We end this section by showing that the optimization of MST-Sp APX-HARD (for fixed k) when hard constraint on the number of points per group is imposed. The proof can be found in the appendix.
Theorem 4.7. Unless = P. any a = poly(n), there is no (1, 1-2 - for the problem of finding the (ks, T.l-cussteiing that maximizes the MST-Sp criterion.
5 Experiments
To evaluate the performance of Algorithms and 2 we ran experiments with 10 different datasets, comparing the results with those of single-linkage and of the traditional k-means algorithm Lloyd (1982) with a ++ initialization (Arthur Vassilvitskii 2007). For the implementation of routine MaxMinSched, employed by Algorithm II used the Longest Processing Time rule. This rule has the advantage of being fast while guaranteeing a 3/4 approximation for the max-min scheduling problem (Csirik al.) 1992). The code for running the algorithms be found at SSizeoonstrrinneSppccinng
https://8 http://..wooeonnnnooooooooeaaaee
Our first experiment investigates the size of the groups produced by single-linkage for the 10 datasets, whose dimensions can be found in the first two columns of Table [ 2 shows the
proportion of singletons for each dataset with the growth of k. For all datasets but Vowel and Mice

---

Table 1: Min-Sp and MST-Sp for the different methods and datasets.
Dimensions
Min-Sp Algo
MST-Sp Algo 2
Algo
k-means
Algo
k-means
anuran
7,195
0.19
0.09
0.05
1.71
1.87
1.01
avila
20,867
12
0.07
0.04
0
0.77
0.81
0.66
collins
1,000
0.42
0.42
0.22
12.42
12.42
8.58
digits
1,797
10
19.74
19.74
13.79
178.22
178.22
145.13
letter
20,000
0.2
0.11
0.07
4.98
5.67
1.98
mice
552
0.79
0.79
0.24
5.66
5.66
2.37
newsgroups
18,846
1
0.17
19
19
8,4
pendigits
10,992
10
23.89
9.08
8.31
215.11
217.01
119.85
sensorless
58,509
0.13
0.08
0.03
1.31
1.36
1.29
vowel
990
11
0.49
0.49
0.11
4.94
4.94
1.84
majority of groups are singletons, even for small values of This undesirable behavior motivates our constraint on the minimum size of a group.
proportion singletons
0.8
newsgroups
pendigits
0.6
digits
collins
vowel
0.2
sensorless
letter
mice
0.0
k (normalized
Figure 2: Proportion of singletons for each dataset with the growth of A
In our second experiment, compare the values of Min-Sp and MST-Sp achieved by algorithms with those of k-means. While k-means is not a particularly strong competitor in the sense that it was not designed to optimize our criteria, the motivation to include it is that k-means is very popular choice among practitioners. Moreover, for datasets with well-separated groups, the minimization of the squared sum of errors (pursued by k-means) should also imply the maximization of inter-group criteria.
Table I presents the results of this experiment. The values chosen for k are the numbers of classes (dependent variable) the datasets, while for the dist function we employed the Euclidean dis- tance. The values associated with the criteria are averages of 10 executions, with each execution corresponding to a different seed provided to k-means. To set the value of L for the i-th execution of our algorithms, we take the size of the smallest group generated by k-means for this execution and multiply it by 4/3. This way, we guarantce that the size of the smallest group produced by our methods, for each execution, is not smaller than that of k-means, which makes the comparison among the optimization criteria fairer.
With respect to the Min-Sp criterion, Algorithm iis at least as good as Algorithm for every dataset (being superior on 6) and both Algorithm | and outperform k-means on all datasets. On the other hand, with respect to the MST-Sp criterion, Algorithm 2 at least good as Algorithm for every dataset (being better on 6) and, again, both algorithms outperform k-means for all datasets. In the appendix, we present additional information regarding this experiment. In particular, we show that

---

Table 2: Running time in seconds single-linkage and our methods.
Dataset
single-linkage
Algo 1
Algo 2
sensorless
93.8
99.4
701.4
newsgroups
274.2
276.4
440.4
letter
4.6
5.9
116.4
avila
4.0
5.5
62.5
pendigits
1.4
2.1
16.0
the MST-Sp achieved by Algorithm 2 is on average 81% of the upper bound Ex= follows from Lemma 4.4 This is much better than the 1/ 1/Hx-1 ratio given by the theoretical bound.
Min-Sp(AA) that
Finally, Table shows the running time our algorithms for the datasets that consumed more time. We observe that the overhead introduced by Algorithm
-inkaee is negligible while Algorithm 2 as expected, is more costly. In the appendix, we show that a strategy that only considers values of L that can be written as [k/22'], for 0..... [log k], in the first loop of Algorithm 2 provides a significant gain of running time while incurring a small loss in the MST-Sp. We note that the log & bound of Theorem is still valid for this strategy.
T w.r.t.
6 Final Remarks
We have endeavored in this paper to expand the current knowledge on clustering methods for optimizing inter-cluster criteria. We have proved that the well-known single-linkan produces partitions that maximize not only the minimum spacing between any two clusters, but also the MST spacing, stronger guarantee. We have also studied the task of maximizing these criteria under the constraint that each group of the clustering has at least points. We provided complexity results and algorithms with provable approximation guarantees.
One potential limitation our proposed algorithms is their usage on massive datasets (in particular Algorithm 2 since they execute Langle-linneee explicitly given, then the ((n2)) time spent by single-linkage is unavoidable. However, the distances can be calculated from the set of points X' then faster algorithms might be obtained.
one many times. If the dist function is
The main theoretical question that remained open our work is whether there exist constant approximation algorithms for the maximization of MST-Sp. In addition to addressing this question, interesting directions for future research include handling different inter-group measures as well as other constraints the structure of clustering.
Acknowledgments and Disclosure of Funding
The authors thank BigDataCorp power for the experiments of an initial version of the paper.
br/) for providing computational
The work of the authors is partially supported by the Air Force Office of Scientific Research (award number FA9550-22-1 12-00755...
The work of the first author is partially supported by CNPq (grant 310741/2021-1).
References
Ahmadi, S., Awasthi, P., Khuller, S., Kleindessner, M., Morgenstern, J., Sukprasert, P., and Vakilian, A. Individual preference stability for clustering. In Chaudhuri, K., Jegelka, S., Song, L., Szepesvari, C., Niu, G., and Sabato, S. (eds.), Proceedings of the 39th International Conference Machine Learning, volume 162 of Proceedings of Machine Learning Research, pp. 197-246. PMIR, 17-23
Jul 2022. hthhttps: wwtphh::t///oeeeeeeeeeeeee http://pppeeeen.eeeeee/e/e mlr ppwss/ vitees/vv62// wwwadim2aaa...............aaaaaa html
10

---

Ahmadian, S., Norouzi-Fard, A., Svensson, O., and Ward, J. Better guarantees for k-means and euclidean k-median by primal- dual algorithms. SIAM J. Comput, 49(4), 2020. doi: 10.1137/ 171311. URL. pattps://doi. org/10 00..0.117188110 1137/18M1173211
Arthur, D. and Vassilvitskii,, S. K-means++: The advantages of careful seeding. In Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '07, pp. 1027-1035, USA, 2007. Society for Industrial and Applied Mathematics. ISBN 9780898716245. URL
https: //dl acm. wwtg//i///..ooe /ttp///d/11...55/12233333 05555/183388..... 1283494
Carlsson, E. and Mémoli, F. Characterization, stability and convergence of hierarchical clustering methods. J. Mach. Learn. Res., 11:1425-1470,
Charikar, M. and Chatziafratis, V. Approximate hierarchical clustering via sparsest cut and spreading metrics. In Klein, P. N. (ed.), Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16-19, pp. 841-854, SIAM, 2017. doi: 10.113771.97816111977782. URL https://doi org/ 1137/ 1. 1.9781611974722.55
Charikar, M.. Guha, S., Tardos, É., and Shmoys, D. B. A constant- approximation algorithm for the k-median problem. J. Comput. Syst. Sci., 65(():129-149) 2002. doi: 10.10066)css:2202211822
URL atttps///do.. org/oo..o... 1006/ 2002. 1882
Cohen-Addad, V., Kanade, V., Collmann-TTeenn F., and Mathieu, C. Hierarchical clustering: Ob- jective functions and algorithms. J. ACM, 66(4):26:1126:44 2019. doi: 10. 145/3321386. URL
https://doi.cot 10. 1145/3321188
Csirik, J., Kellerer, H., and Woeginger, G. J. The exact lpt-bound for maximizing the minimum completion time. Oper. Res. Lett. 1(55):8112288) 1992. doi: 10. 00.100166066666377729000000 6377 (92) 90004-M
URL pattts://doos wtt///o..og//////ooeo
Dasgupta, S. A cost function for similarity based hierarchical clustering. In Wichs, D. and Mansour, Y. (eds.), Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, Cambridge, MA, USA, June 18-21, 2016, pp. 118-127, ACM, 2016. doi: 10.1145/ 0897518.2897577 URL httts://pp//ot http///oi.orgg/////// 1tgg/10.114//299555. 2897527
Davies, D. L. and Bouldin, D. W. A Cluster Separation Measure. IEEE Transactions on Pattern Analysis and Machine Intelligence, PAMI-12):224-227, April 1979. ISSN 1939-3539, doi: 10. 109/TPAM..19999 197.999699999, Conference Name: IEEE Transactions on Pattern Analysis and Machine Intelligence.
Frieze, A. M. and Jerrum, M. Improved approximation algorithms for MAX k-cut and MAX BISECTION. Algorithmiia. 18(1)66-811, 81, 1997. doi: 10.1007/BBF02523688. URL https 1007 10..1000//BFSS BFF2523688
7/doi //doi.org//ii. org/10. 1ttg//...007//811
Garey, M. R. and Johnson, D. S. Computers and Intractability: A Guide the Theory of NP-Completeness (Series of Books in the Mathematical Sciences). W. H. Free- man, first edition edition, 1979. ISBN 0716710455. URL http://www amazon com/ Coon/Compterss-e http://pppttrr--ntaaaaaaaalaaaaa Mop- Mathematiical-ciennees 0716710455
Gong, Z., Zhong, P., and Hu, W. Diversity in machine learning. leee Access, 7:64323-64350 2019.
Gonzalez, T. F. Clustering to minimize the maximum intercluster distance, Theor Comput. Sci., 38:293-306, 1985. doi: 10. 1..116660334-33755559022--- URL htttps://dot (eidoi..rg//il org/10.11000 0304
9
Gupta, D. and Ghafir, S. An overview of methods maintaining diversity in genetic algorithms. International journal of emerging technology and udvanced engineering, 255):56-60, 2012.
Hennig, C., Meila, M., Murtagh, F., and Rocci, R. Handbook of Cluster Analysis. Chapman and Hall/CRC, 2015.
Hofmeyr, D. Connecting spectral clustering to maximum margins and level sets. The Journal of Machine Learning Research, 21(1))630-66) 2020.

---

Jain, A. K., Murty, M. N., and Flynn. P. J. Data clustering; A review. ACM Comput. Surv., 31(3): 264-323, September 1999. ISSN 0360-0300.
Kleinberg, M. An impossibility theorem for clustering. In Advances in neural information processing systems, 2002.
Kleinberg, M. and Tardos, É. Algorithm design. Aadison-Wesleyy 2006. ISBN 978-0-321-37291-8.
Lloyd, Least squares quantization in pem. IEEE transactions on information theory, 28(2): 129-137, 1982.
Moseley, B. and Wang, J. R. Approximation bounds for hierarchical clustering: Average linkage, bisecting k-means, and local search. In Guyon, I., von Luxburg, U., Bengio, S., Wallach, H. M., Fergus, R., Vishwanathan, S. V. N., and Garnett, R. (eds.), Advances in Neural Information Processing Systems 30: Anmual Conference on Neural Information Processing Systems 2017, December 4-9, 2017, Long Beach, CA, USA, pp. 3094-3103, 2017. URL neurips
http:///aa..cceeeaaaaaa/e///eee0 Abstract.html
Rousseeuw, P. Silhouettes: a graphical aid to the interpretation and validation of cluster analysis. Comput. Appl. Math., 20(1) (MM1):53666) 65, 1987. ISSN 0377-0427. doi: htp::/dx.doi. www.ddxddooorrgg....... / 1016/ 0377-0427787)901155-7 URL htt.hhtt:p/pttaae acm. org/ citation..... cfm?id=38772
Roy, A. and Pokutta, S. Hicrarchical clustering via spreading metrics. In Lee, D. D., Sugiyama, M., von Luxburg. U., Guyon, I., and Garnett, R. (eds.). Advances Neural Information Processing Systems 29: Annual Conference Neural Information Processing Systems 2016, December 5-10. 2016, Barcelona, Spain, pp. 2316-2324, 2016. URL https: http::pps///roocedngg..... nww.ineeripp... cc/
Abstract html
Woeginger, G. A polynomial-time approximation scheme for maximizing the minimum machine completion time. Oper. Res. Lett., 20(()) 1997. doi: 10. 10.001//1166--33779900005-- URL 1tLL
Zahn, C. T. Graph-theoretical methods for detecting and describing gestalt clusters. IEEE Tronsactions on computers, 100(1):68-00)) 1971.
12

---

A Properties of Minimum Spanning Trees
Theorem A.1 (Cut Property, Kleinberg & Tardos (006)), Property 4.17.). Let G (V, E) be a graph with distinct weights on its edges. Let S C V be non-empty cut in G, If is the edge with minimum cost among those that have one endpoint in and the other one V S, then belongs to every MST for G
Theorem A.2 (Cycle Property. Kleinberg & Tardos (2006), Property 4.20.). Let G = (V, E) be graph with distinct weights its edges and let C be a cycle in G. Then, the edge with the largest weight in does not belong to any minimum spanning tree for G.
The following characterization of MST's will be useful. Its correctness follows directly from the cycle property.
Theorem A.3. Let G = (V, F.) be graph with weights on its edges. A spanning tree T for G is MST for G if and only if for each edge e ue E, the weight w(e) of satisfies w(e) 2 w(e') for every edge é' in the path that connects
in T.
B Proof of Lemma 3.1
We need the following proposition.
Proposition B.1. Lei C' be a k-clustering for instance T and let T" be MST for Ge. Moreover, let C₁ and Cý be groups of C' such that spacing(C), (7)) = Min-Sp(C"), Then, the tree T that results from the contraction of the nodes C₁ and C2 in T" is a MST Gcs, where Co is the (k- (k--1--oh (k-uucccssteriin obtained from C' by merging C₁, and Cr-
Proof. We show that 7 satisfies the conditions of Theorem A.3 when G = Gea. For that, we will use the fact that T' satisfies the conditions of Theorem A.3 when G -Ge.
Let and be nodes of T For the sake of contradiction, we assume that edge ry does not satisfy the conditions of Theorem A.3 when G Gç and T T Let w" be the weight of edge zy and let be an edge in the path that connects to in T such that w(e) > w". We have two cases:
Case 1) x # C₁ CJ and + C2 U Cj. Then, is also an edge in the path that connects x to y in TV. This implies that zy does not satisfy the required conditions when G = Ge and T = T", which is contradiction.
Case 2) = C or + C.UCC Let us assume w.l.o.g. that x = C. UGC Let w/ and we be, respectively, the weights of the edges (y, Cf)) and (y. Cý) in Gc. We have that w = min w// w/}.
Let us assume w.l.o.g. that w² w/. Then, e is also edge in the path that connects y C in TV. Again, this implies that ry does not satisfy the required conditions when G Ge and T = T" which is contradiction.
Proof of Lemma 3.1
It follows from the previous proposition hat the tree T that is obtained by contracting the - 1 cheapest edges of T is MST for Gç--,, where C:-1 is clustering for instance I that contains groups. The cheapest edge of Ti is exactly the i-th cheapest edge of T. Thus,
(k - Min-Sp(CC wi. u.
Similarly, wiSh is exactly the minimum spacing of a clustering, with (k: - (i -i-ii-1 groups, that is obtained by Lingle-linkage for instance Thus, follows from Theorem 2.1 that w 2 W
C Proofs of Section
C.1 Proof of Lemma
Proof. Let T be the MST for Gc.. If we remove the f-1 most expensive edges of T we obtain forest F' with l connected components. The clustering C comprised by & groups in
13

---

which the ith group corresponds to the ith connected component of F is (e, L) clusteringg and Min-Sp(C;)) wh+1+1'
Let OPT be the Min-Sp of the (t, clluusterinng with maximum Min-Sp. Thus, by Theorem 4.1 Min-Sp(A') 2 OPT 2 Min-Sp(CT) = -
C.2 Proof of Theorem 4.2
Proof. We make reduction from the (2) 3-PARTITION problem. Given multiset S = {$1,..., $ of positive integers that satisfies Σ, 8; = m''' the 3-PARTITION problem consists of deciding whether or not there exists a partition of S into m triples such that the sum of the numbers in each one is equal to T. In the (T) (T/4, /4, T T/))-restiicee 3-PARTITION problem. there is an additional requirement that each number of S should be in the interval (T/4, T 22). This problem is strongly NP- NP-COMPLETE Garey & Johnson (1979)
The instance / (X, k, L,, dist) for clustering problem is built as follows: we L. T, k = m. for i = 1, the same group X; is 1 while the distance between points different groups is a + 1. We set X' == Xi U...U ....UA Xam- Note that we are employing a eseudo-polynomial reduction but this is fine since the (I/4, 1 3-PARTITION problem is strongly NP-COMPLETE.
3m let X; be a set with points so that the distance between points in
Let us assume that there is an (1, (1.11/)-apppal apprrxxixxinnnnnnn for our problem and let C be the clustering returned by this algorithm for instance I. We argue that the answer to the 3-PARTITION problem is 'YES' if and only if Min-Sp(C) = a 1.
First, we show that if the answer is 'YES', there is k-clustering C* for I with Min-Sp(C*) In fact, let .i...., Sm be a solution of the 3-PARTITION problem and let { 8 8ig) the numbers in S, Let C* be k-clustering where the ith group is comprised by all points in Lx U.Y, U x Clearly, each group has L points and the Min-Sp of this clustering is a + 1. Since our algorithm is a (L, approximaatnonnn it returns a clustering C with Min-Sp(C) 2 (a + 1)/a. Since the Min-Sp of any clustering for instance I is either or a + we have that Min-Sp(C)=a +
1.
On the other hand, if the clustering has Min + then all points in X, for each i, must be in the same group. Moreover, due the restriction that every [X = 8, E (L/4, L/2), we should have exactly 3 X's in each of the m groups. Thus, the answer is 'YES'.
C.3 Proof of Theorem 4.7
The proof is very similar to that of Theorem 4.2
3-PARTITION problem. Given a multiset 5 = {81,.... } of positive integers that satisfies Σ. 8, = mT, the 3-PARTITION problem consists of deciding whether or not there exists a partition of S into m triples such that the sum of the numbers in each one is equal to T. the (T/ /4, -es))rrst 3-PARTITION problem, there is an additional requirement that each number of S should be in the interval (T/4,T/2). This problem is strongly NP-COMPLETE Garey & Johnson (1979)
Proof. We make reduction from the
The instance I = (X, k L, dist) for our clustering problem is built as follows: we set L = T, k m; for 1, 3m let X; be a set with s; points so that the distance between points the same group X; is 1/2 while the distance between points in different groups is a. We set X' = X2 U. U...
Let us assume that there an (1, k مل=ي)) aaprroximation for our problem and let be the clustering returned by this algorithm for instance 1. We argue that the answer to the 3-PARTITION problem is 'YES' if and only if MST-Sp(C) = (k= - 1)a.
First, we show that if the answer is 'YES', there is a k-clustering C* for I with MST-Sp(C*)) = (k: - 1)a. In fact, let Si...., Sm be solution of the 3-PARTITION problem and let {s., Siz Sig the numbers in S.. Let C* be a k-clustering where the ith group is comprised by all points in X, U UY,, U X,y. Clearly, each group has L points and the MST-Sp of this clustering is (k 1)a.
Since our algorithm is (1, h-T + >(k-TT)) ( approximaaio it returns a clustering C with MST-Sp(C) (I: - 2)ax + 1. Since the MST-Sp of any clustering for instance / is either (k: 1)xx or at most (k- 2)a + 1/2 we have that MST-Sp(C)=(K l)a
14

---

Table Comparison of MST-Sp of Algorithm 2
with the upper bound given by Lemma
k
MST-Sp
Σi= Min-Sp(A()
Approximation Ratio
1/HR-1
anuran
10
1.87
2.42
0.77
0.35
avila
12
0.81
1,48
0.55
0.34
collins
30
12.42
13.81
0.9
0.33
digits
10
178.22
201.47
0.88
0.32
letter
26
5.67
5.76
0,98
0.31
mice
8
5.66
7.12
0.79
0.31
newsgroups
20
19
19
1
0.3
pendigits
10
217.01
303.37
0.72
0.3
sensorless
11
1.36
2.23
0.61
0.29
vowel
11
4.94
5.57
0.89
0.29
On the other hand, if the clustering has Min-Sp (k: 1)a then all points in Xr for each must be in the same group. Moreover, due to the restriction that every |24 = E (L/4, L/2), we should have exactly X/'s each of the m groups. Thus, the answer 'YES'.
D Experiments: Additional Information
Experiments were run an Ubuntu 20.04.5 LTS with 40 cores and 115 GB RAM. The repository of the project at atttps://ant //to::////nmmmuus 4open. wcwssciieeeeeeeee www.ee/e/iieooossriiinnnaaeeeeee tains the code and instructions needed generate the experimental data analyzed in the paper.
(anaaciinnne-6 con-
D.1 MST-Sp: comparison between empirical results and upper bound of Algorithm 2
As mentioned in Section Algorithm 2 can practice obtain clusterings that are much closer to the optimal MST-Sp than the prediction guaranteed by Theorem 4.6 In Table we present, for each dataset: the average MST-Sp obtained by Algorithm the upper bound on the MST-Sp given by the sum of the Min-Sp for all partitions found by an execution of the algorithm; the approximation ratio of Algorithm?? 2 given by its MST-Sp divided by the upper bound; and the theoretical approximation ratio 1/Hx-1 from Theorem 4.6
For all datasets, Algorithm 2 performs significantly better than its theoretical approximation ratio. The smallest gap between theoretical and empirical result occurs for avile wvila dataset, in which the algorithm 21 percentage points closer to the optimal MST-Sp than Theorem 4.6 guarantees; On the other extreme, for dataset newsgroups, it actually achieves the best possible MST-Sp. These results increase our confidence that Algorithm 2 is good option for finding separated groups.
D.2 Average size smallest clusters
Table presents the average size of the smallest group generated by Algorithms and and k-means. Values tend to be close across all algorithms, and for all iterations of the experiments the smallest group returned by Algorithms [ and
at least large as the smallest group from the corresponding k-means clustering; recall that is set as 4s 1s/3, where is the size of the smallest group produced by k-means. In particular, thanks to the rule of iterating from the largest cluster to the smallest when building our k-clustering from an É-clustering, the theoretical possibility that the smallest group induced by Algorithm 2 is 1/2 of the desired size does not appear to happen practice.
D.3 Fast version of Algorithm 2
As mentioned in Section the log bound Theorem 4.6 is still valid for Algorithm if, instead of investigating all values of ? from 2 to k; considers only the values that can be written as [k/22], for I = 0,..., log k.. In Table we compare the results of this fast version of the algorithm with those of the full version.
15

---

Table Average size of the smallest cluster in a k-clustering, per algorithm and dataset.
Dimensions
Average size of smallest cluster
n
k
Algorithm
Algorithm
k-means
anuran
7.195
10
264.5
266.7
264.1
avila
20,867
12
85.3
85.4
83.2
collins
1,000
30
7.7
7.7
digits
1,797
10
96.2
96.2
92.7
letter
20,000
26
192
258.7
191.5
mice
552
8
47.6
47.6
47
newsgroups
18,846
20
188.1
188.2
188.1
pendigits
10,992
10
483.2
476.4
463.8
sensorless
58,509
11
1,842.5
1,725.5
1,655.6
vowel
990
11
57.9
57.9
57.9
Table 5: Min-Sp, MST-Sp and execution time for Algorithm 2
Dimensions
MST-Sp
Time (seconds)
k
Fast
Full
Fast
Full
anuran
7,195
1.71
1.87
2.55
6.77
avila
20.867
12
0.77
0.81
20.47
62.51
collins
1,000
30
12.42
12.42
0.76
4.48
digits
1,797
10
178.22
178.22
0.55
1.78
letter
20,000
26
5.66
5.67
23.44
116.44
mice
552
8
5.66
5.66
0.27
0.44
newsgroups
18,846
20
19
19
307.58
440.38
pendigits
10,992
10
215.11
217.01
6.13
16.02
sensorless
58,509
11
1.34
1.36
274.00
701.42
vowel
990
11
4.94
4.94
0.18
0.59
Even considering the overhead of running the single-linkage algorithm, which cannot avoided for both versions of Algorithm 2 we see reduction of at least 30% in the algorithm's 's running time when using the fast version. The loss in terms MST-Sp, on the other hand, less than 10% in the worst scenario, and in 5 of the 10 datasets analyzed both versions return the same clustering.
D.4 Distribution of results for Min-Sp and MST-Sp
Figures 3 and show the boxplots for the Min-Sp and the MST-Sp, respectively, per dataset and algorithm. Algorithm 2 presents some large variations, when compared to both k-means and Algo- rithm [ in terms of Min-Sp (Figure 3 for some datasets; as is designed to maximize the MST-Sp, this behavior in the other metric presented here should not be concerning. Also in terms of Min-Sp, both algorithms presented in the paper clearly outperform k-means in almost all datasets, even considering the variation in results. The same can be said for the MST-Sp (Figure 4 in which, additionally, the range of results returned by Algorithm) 2 much more in line with those returned by the other algorithms.
D.5 Trade-off between size of smallest cluster and inter-group separability criteria
In Figure we present scatterplots for our 5 smallest datasets showing how the quality of the
clusterings generated by Algorithms and [2 (ond (considerin,,, respectively, the Min-Sp and the MST-Sp as criteria) increases as we allow for clusters of smaller sizes. For all datasets, as expected, allowing for smallest clusters leads to higher Min-Sp and MST-Sp. presented in this paper can be used not only to find a good partition with a hard limit the size of the smallest cluster, but also to find the best balance between minimum size and good separation of clusters.
still noteworthy that the algorithms
16

---

algorithm
0.25
km
algo1
0.20
algo2
0.15
0.10
0.05
0.00
anuran
sensorless
dataset
1.0
algorithm
algo1
0.8
algo2
0.6
0.4
collins
mice
newsgroups
vowel
dataset
algorithm
km
algo1
20.0
algo2
17.5
15.0
7.5
5.0
digits
pendigits
dataset
Figure 3: Boxplots of the Min-Sp per dataset and algorithm.
17

---

algorithm
algo1
algo2
4-
3-
2
1
avila
letter
sensorless
dataset
algorithm
algo1
15.0
algo2
12.5
10.0
7.5
5.0
2.5
collins
mice
newsgroups
vowel
dataset
algorithm
220
km
algo1
200
algo2
180
140
120
digits
pendigits
dataset
Figure 4: Boxplots of the MST-Sp per dataset and algorithm.
18

---

datasel anuren
dataset anuran
0.8
0.7
0.6
MinSpp
NST-50
0.5
0.4
4-
0.3
0.2
100
200
400
dataset vowel
dataset vowel
0.70
7.5
Min 50
0.60
6.0
Ga Reco
0.50
10
20
40
60
10
20
18
0.550
17
0.525
16
0.500
15
13
0.400
12-
0.375
11
10
12
14
8
10
12
14
dataset digits
dataset digits
28
26
Gennce disssto Seo Re0r
Mn-Sp
MST-Sp
220
daaere Roc fof
22
200
20
dataset mice
dataset mice
1.4
12
1.3
1.-
10
Min-Sp
MST-Sp
1.1
9-
0.0
1.0
0.9
6g trc og
0.8
10
30
10
20
40
50
smallest
(a) Algorithm
(b) Algorithm smallest cluster vs. MST-Sp.
smallest cluster vs. Min-Sp.
Figure Trade-off between the size of the smallest cluster and the separability criteria.
19

---

Table Maximum standard deviation of MST-Sp for Algorithm 2
Dimensions
MST-Sp
μ
max
anuran
7,195
1.87
avila
20,867
12
0.81
collins
1,000
12.42
digits
1,797
10
178.22
letter
20,000
5.67
0.34
mice
552
5.66
newsgroups
18,846
19
pendigits
10,992
10
217.01
sensorless
58,509
1.96
0.002
vowel
990
11
4.94
Table 7: Quadratic loss (k-means cost) for Algorithms land
Dimensions
Loss (relative to k-means) Algorithm
k
Algorithm
anuran 7,195
10
2.50
2.07
avila
20,867
12
2.81
2.81
collins
1,000
30
2.33
2.33
digits
1,797
10
1.33
1.33
letter
20,000
26
2.30
2.52
mice
552
8
2.52
2.52
newsgroups
18,846
20
1.05
1.05
pendigits
10,992
10
2.18
2.10
sensorless
58,509
4.32
5.25
vowel
990
11
2.07
2.07
D.6 Effect of randomness on Algorithm 2 results
While Algorithm iss fully deterministic, in Algorithm 2 the split of clusters from an f-clustering to turn it into k-ulustering is performed randomly. In practice, however, this does not affect the results of the algorithm.
For each dataset, we ran 10 seeded iterations of Algorithm 2 for each value of I used in the experiments. We then calculate the standard deviation of the MST-Sp for each value of L. As shown in Table/o, for 8 of the datasets analyzed the MST-Sp of the clustering returned by Algorithm 2 is always the same for given value of L; for letter and sensorless there some variation, but very small compared to the average MST-Sp returned by the algorithm.
D.7 Relative quadratic loss for Algorithms 1 and 2
In Table we present the quadratic loss both Algorithm I and Algorithm aas a multiple of the loss incurred by the k--maans algorithm, which is specifically designed to minimize this loss. As expected, since both algorithms were devised for maximizing inter-group criteria, they perform poorly light with the sole exception of the newsgroups dataset, for which
of this intra-group loss function both algorithms incur loss only 5% above that of k-means. Across datasets, the performance of both algorithms is similar for this loss, with only small variations.
20


Reviews:
[{"review_id": "sFdRm3his2", "reviewer": "Reviewer_Z252", "summary": "The paper presents a body of theoretical results addressing the problems of minimum-spacing and minimum spanning tree clustering; both based on the concept of finding clustering solutions which maximise the inter-cluster distance(s). The former maximises the distance between the pair of closest clusters while the latter maximises the total distances between clusters along a tree connecting them (where set distances are defined as the minimum pairwise distances between elements in different sets).\n\nThe single-linkage agglomerative method is known to maximise inter-cluster distances but is also known to have poor properties empirically (notably the chaining effect and isolation of \"outliers\" and \"noise\"  over the construction of entire clusters). Based on this the authors propose imposing size-constraints which bound the size of the smallest cluster.\n\nThe authors show that hard constraints of this type for the two objectives studied are APX-hard, and so propose relaxations which allow a (1-\\epsilon) factor on the minimum cluster size but admit polynomial time algorithms for the minimum spacing, and in the case of the minimum spanning tree relaxations which also involve the average cluster size relative to the \"hard constraint size\" (being a more substantial relaxation the more balanced the cluster sizes need to be) as well as an approximation factor on the objective function given by the inverse of the k-1 th harmonic number (k being the number of clusters).\n\nThe paper concludes with some experiments documenting the performance of their proposed algorithms.", "questions": "None which I can think of. Good work", "limitations": "None noted", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "The work is extremely thorough and addresses an important problem, which is that maximum inter-cluster distances are very intuitive as objectives for clustering but have poor robustness. The size constraint proposed is natural and intuitive, and the authors have clearly done more than their due diligence in studying the extending the problem.\n\nThe paper is also, subject to some technical knowledge, clear and easy to follow.", "weaknesses": "Nothing substantial. Arguably some missed pieces of literature:\n- Early work on MST clustering: Zahn, Charles T. \"Graph-theoretical methods for detecting and describing gestalt clusters.\" IEEE Transactions on computers 100.1 (1971): 68-86.\n- Connection between Min-Sp and spectral clustering: Hofmeyr, David P. \"Connecting spectral clustering to maximum margins and level sets.\" The Journal of Machine Learning Research 21.1 (2020): 630-664.\n- Maximum Margin Clustering: Xu, Linli, James Neufeld, Bryce Larson, and Dale Schuurmans. \"Maximum margin clustering.\" Advances in neural information processing systems 17 (2004).\n\nTypos and similar:\n- Line 111: plural of vertex is \"vertices\"\n- Lines 126-7: \"the the cut property... and the cut property\"???\n- Include the explicit version of PTAS", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We greatly appreciate your kind words! We will be sure to review our text for typos and to incorporate the papers you mentioned to our Related Work section.\n"}, {"review_id": "nWqwywwQhB", "reviewer": "Reviewer_FmRy", "summary": "The paper considers the following problem: given a metric space on a set of $n$ points and a parameter $k$, partition the points into $k$ clusters $C_1, \\ldots, C_k$. The paper considers two objective functions: consider a metric  with vertices $X$ as the set of clusters and distance between two clusters being the minimum distance between two points belonging to these clusters respectively. The first objective is to maximize the minimum distance between any two points in $X$, and the second objective is to maximize the cost of the min. spanning tree on $X$. It is easy to show that the greedy algorithm for MST can be modified to solve these two problems in polynomial time (essentially run the Kruskal's algorithm till only $k$ components remain). \n\nHowever, the authors observe that this can lead to skewed clusters with some clusters being too small. So they propose the following problem: consider the same settings as above, but now each cluster must have at least $L$ points, where $L$ is another parameter provided in the input. They give the following polynomial time guarantees for the two problems: (i) for the max min. cluster separation objective, they give an algorithm of optimal value but each cluster has size at least $L(1-\\epsilon)$, where $\\epsilon > 0$ is any constant, and (ii) for the MST objective, they give an algorithm of objective value at least $1/\\log k$ times the optimal value, and each cluster size is at least $L(1-\\epsilon)$. They show that  modifications of the greedy heuristic along with known results for a schedling problem work for the first problem, whereas the second one requires more details.", "questions": "1. It is not clear if the problems are non-trivial or follow from known ideas/techniques. \n\n2. Please explain if instead of placing lower bound of $L$, placing an upper bound of $L$ will change the problem significantly.", "limitations": "No negative impact.", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "1. Introduce an interesting problem. \n2. Give near-tight bounds for the max min cluster separation problem, and leave an interesting open problem for the max min spanning tree problem.", "weaknesses": "It seems to me that the two problems can be solved in a simpler manner without appealing to the greedy heuristic. Assume that the metric on the $n$ points is given by a weighted graph $G$. \n\n1. First consider the max min cluster separation problem: suppose we know the optimal value $T$ (which we can guess by binary search). Now remove all edges of length less than $T$ from the $G$:  these edges cannot appear between two distinct clusters. Now consider the components formed -- they should be more than $k$. Now merge these components using the scheduling problem used in the paper. \n\n2. For the max. mst problem: again suppose we know the optimal value, say $T$. Now consider the optimal tree on the $k$ vertices $X$ -- call this tree $F$. Ignore the edges of cost less than $T/2k$ from $F$ -- the total cost of such edges is at most $T/2$. Now consider the edges in $F$ whose cost lies in the range $[T/2k, T]$. Divide this range into $\\log k$ buckets of exponentially increasing range. So there is an index $i$ such that the edges in $F$ (call these edges $E_i$) with cost in the range $[\\frac{T}{2^{i+1} k}, \\frac{T}{2^i k}]$ have total cost at least $\\frac{T}{2 \\log k}$. Now remove all edges of length at least $\\frac{T}{2^{i+1} k}$ from $G$. It is not difficult to show that if $E_i$ has $a$ edges, then removing such edges from $G$ will create at least $a$ components. Now we form clusters so that no cluster contains points from two distinct components.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer!\n\nHowever, we are a bit surprised by his/her evaluation, as discussed below.\n\n**Score**\n\nIt is not clear what are the soundness and presentation problems in our work that justify a score 2 for these dimensions; there is no comment about it.\n\n**Weakness**\n\nThe weakness that the referee identified in our work is that “the two problems can be solved in a simpler manner without appealing to the greedy heuristic”.\n\nWe do not see why the solutions that the referee proposed are simpler than ours. Even if they are, we believe that our solutions are simple enough, as we managed to implement them without any major obstacles.\n\nMore importantly, as far as we understand, the solution proposed for the min-sp is essentially proposed in the paper while the one for the minimum MST is not detailed enough, which makes it hard to verify its correctness and how simple it is. We explain below: \n\n1. The solution proposed for the maximization of min-sp is very similar to the one we mention in lines 197-199. The only differences that we identify are:\n\n    - instead of adding edges (Kruskal), the proposed solution removes them.  \n\n    - the proposed binary search does not run in strongly polynomial time (due to the logarithm on the maximum possible cost) while ours does.      \n\n2. Important details are missing from the solution for the MST-sp:\n    - the reviewer mentions an index $i$ that will be used to \"remove all edges of length at least $\\frac{T}{2^{i+1}k}$ from $G$\". How can we find this index without having the tree $F$? Shall we try all the possibilities for $i$?          \n  \n    - The last step of this solution is to \"form clusters so that no cluster contains points from two distinct components.\" It is not clear how this step shall be implemented. **More seriously**, we agree that at least $a$ components are created when the edges are removed from $G$, but it may happen that more than $k$ components can be created (some of the $k$ clusters of $F$ may be split into many components); in this case, the proposed rule (“no cluster contains points from distinct components”) will not lead to the production of $k$ clusters. Wouldn't this be a problem in the proposed solution?\n\n**Questions:**\n\n*It is not clear if the problems are non-trivial or follow from known ideas/techniques.*\n\n**Reply:** We put considerable energy into finding meaningful and tractable formulations and also coming up with approximation algorithms and inapproximability results. The relatively simple proofs presented in the paper - in particular, those from Section 3 that the reviewer classifies as “easy” in his/her summary - are the result of successive refinement; the first versions were much messier and more intricate than the current ones. Many researchers see simplicity as a virtue rather than a weakness. \n\n*Please explain if instead of placing lower bound of $L$, placing an upper bound of $L$\n \twill change the problem significantly.*\n\n**Reply:** The techniques we used do not seem to apply directly when we use upper bound constraints. \n\nIn light of the above discussion, we kindly request that the reviewer revise his/her scores."}, {"review_id": "bzAVBTDB8B", "reviewer": "Reviewer_FsJN", "summary": "This paper considers the problem where we want to cluster $n$ points into $k$ clusters with the clustering objective trying to maximize the minimum distances between clusters (either the actual minimum distance or the weight of an MST defined between clusters). The authors show that greedy agglomerative clustering (stopping when $k$ clusters are formed) with single-linkage optimizes both objectives. The authors also consider the scenario where the user specifies a minimum cluster size as an additional constraint. Approximation algorithms for this setting are presented and hardness of approximation results are shown. Empirical results are shown on publicly available datasets.", "questions": "* What is another example application other than the diversity example given on lines 34-38? \n* What benefits do Min-Sp and MST-Sp have over other clustering objectives? Why would a user choose this objective over another objective?\n* How might one select the minimum cluster size? Could this be an issue just as difficult as selecting the number of clusters $k$?", "limitations": "Limitations are adequately addressed.", "rating": 3, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "* The paper is well-written\n* The problem is interesting from a theoretical perspective\n* The theoretical results are sound, albeit not surprising", "weaknesses": "* The motivation for the problem setting is very weak. It is unclear where this would be used in practice.\n* The results presented are probably not of high interest to the NeurIPS community. The theoretical results are solid, but not surprising, and the applications of this method are not presented. Could this be more appropriate for a theory venue?\n* The experimental results do not convey much about the performance of the algorithms except for their relative performance, which is not very dramatic. Are there other experiments that could be run to show why someone would want to use Algorithm 1 or 2 over another approach?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks again for your time and effort! \n\nWe discuss applications and the fit for Neurips in our comments addressed to all reviewers.\n\nQuestions:\n\n*The experimental results do not convey much about the performance of the algorithms except for their relative performance, which is not very dramatic. Are there other experiments that could be run to show why someone would want to use Algorithm 1 or 2 over another approach?*\n\n**Reply:** Apparently, you are only taking into account the experimental results presented in the body (main submission). Is this the case? \n\nBy taking into account also the supplemental material, we feel that our experiments do more than show the algorithms’ relative performance:\n\n1. In Table 1, we show that our algorithms clearly outperform $k$-means for the separability metrics analyzed in the paper. We believe this is what you are referring to when talking about relative performance.\n\n2. In Table 3, we compare the results of Algorithm 2 with the upper bound of MST-Sp given by Lemma 4.4, showing that the results are frequently much closer to the optimal than the approximation guaranteed by Theorem 4.6. That is, the absolute performance of this algorithm is also good (close to the optimal in many cases).\n\n3. In Table 5, we present the results of a different, faster version of Algorithm 2, which are quite close to, and frequently the same as, the results of the algorithm’s full version. That is, we can achieve good results (in both relative and absolute terms) quite fast if necessary.\n\n4. In Figures 3 and 4, we show that the results of Algorithms 1 and 2 for their respective separability metrics are robust, in two senses: \nTheir results do not vary much across iterations.\nTheir results are clearly superior to $k$-means, even considering possible variations across iterations.\n\n5. In Figure 5, we show the trade-off between the minimum cluster size and the separability criteria. This can be important when trying to establish the optimal minimum cluster size (see also our answer to your question below).\n\n\n*What is another example application other than the diversity example given on lines 34-38?*\n\n**Reply:**  See our comment directed to all referees.\n\n*What benefits do Min-Sp and MST-Sp have over other clustering objectives? Why would a user choose this objective over another objective?*\n\n**Reply:** One may choose these objectives to generate groups that are far from each other because these objectives are natural (easy to understand) and they have algorithms with provable guarantees that are fairly simple to implement (the ones we proposed here).\n\n*How might one select the minimum cluster size? Could this be an issue just as difficult as selecting the number of clusters?*\n\n**Reply:** We view the minimum cluster size as an issue that depends largely on the specifics of each use case.  We present in Figure 5 of the supplementary material plots representing the trade-off between minimum cluster size and the separability criteria. Analyzing this trade-off may be very useful when deciding on the minimum cluster size; as we mention in section D.5,  “the algorithms presented in this paper can be used not only to find a good partition with a hard limit on the size of the smallest cluster, but also to find the best balance between minimum size and a good separation of clusters.”\n"}, {"review_id": "UCAaNo6NjL", "reviewer": "Reviewer_GUvh", "summary": "The authors of this paper consider metric clustering problems, where the goal is to maximize inter-clustering objectives. Such objectives measure how \"distinct\" different clusters are. The first objective they consider is the minimum spacing one (MS). According to this, the goal is to maximize the minimum distance between any resulting clusters, where the minimum distance between clusters is naturally defined as the minimum distance between any of their points. The second objective they consider is maximizing the minimum spanning tree (MST) distance. Here, the MST distance is defined on the complete graph representing the resulting clusters. I would say that the latter objective captures a more general/global notion of connectivity/similarity compared to the earlier one.\n\nAt first, the authors state that the single-linkage algorithm by Kleinberg and Tardos maximizes the MS objective, and this is something already known in the literature. However, they also show that this algorithm satisfies MST as well. More interestingly, they show that any algorithm satisfying MST will also satisfy MS.\n\nMoving forward, the authors tackle a constrained version of the problem, where besides minimizing the appropriate objective, they want to create clusters of size at least L, for some given L. For the constrained versions of the their problems, they give their most algorithmically involved results, which consist of bicriteria approximation algorithms followed by corresponding lower bounds.", "questions": "1) I think that the following works are a bit related to yours. Under the broader umbrella of inter-group clustering. The goal in those papers is to make sure that on average, each point is closer to points in its own cluster compared to other clusters. To me this feels like an inter-group objective.\n\nhttps://arxiv.org/abs/2006.04960\nhttps://arxiv.org/abs/2207.03600\n\n2) In Figure 1 where you say that the left clustering is not natural, it is not really clear what you mean. I suppose that you want to show that solving MS can negatively impact MST.", "limitations": "N/A", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "1) The paper is technically solid and well-written.\n\n2) The inter-clustering objective is cute and quite novel. From the theoretical perspective it opens up a new direction for clustering research.\n\n3) The results are pretty tight. The characterization of Theorem 3.3 is solid and impressive and the lower bound algorithms are accompanied by the proper inapproximability results.", "weaknesses": "1) From a practical motivational perspective, I am not convinced about the use-cases of such a model. The authors should have elaborated more there, giving more fitting applications. This is honestly my only concern for this paper. I can easily see this paper getting into a pure algorithms conference like APPROX-RANDON or ICALP, but I feel like for NeurIPS standards there should have been a more detailed discussion on how this inter-group model (with the objective functions considered) could fly in real-life scenarios (perhaps by giving concrete specific use-cases). Also, from a practical perspective I can't see the necessity of the lower bound constraint. \n\nIf it wasn't for the lack of motivation my score would most likely be higher. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We are quite happy that you appreciated our work! \n\nIn our comment directed to all referees, we discuss the fit for Neurips and potential applications.\n\nQuestions:\n\n1. About the papers you mentioned \n\n    **Reply.** Thanks for pointing out the papers! Indeed, they are related to ours and we will cite them in our new version. \n\n2. In Figure 1 where you say that the left clustering is not natural, it is not really clear what you mean. I suppose that you want to show that solving MS can negatively impact MST.\n\n    **Reply.** The main point of the figure is that saying that single-linkage maximizes the minimum spacing may not fully describe its behavior, as other partitions that do the same may look very distinct from that generated by single-linkage. We will try to make this clearer in the revised version of the paper.\n"}]

Author rebuttal:
**To all Reviewers**

We thank all the referees for your time and effort. We are happy that some referees classified our work as solid and extremely thorough and that all referees found our problem interesting.

We have specific comments for each referee, but in the current one, we discuss potential applications for our work and the issue of whether it is interesting for the Neurips community, 

**Fit to Neurips Community**

 Our paper is essentially dedicated to studying problems that optimize the same functions that are optimized by the Single-Link algorithm, the Min-SP, and the Sum-Sp, with the latter being identified in our work. The Single-Link algorithm is a classical algorithm and it is available in most (if not all) Machine Learning packages. Moreover, it has been the subject of a number of studies that were published in Neurips and JMLR  such as  [Kleinberg, Neurips 2002, cited in the paper],  [Xu, Linli et. al, Neurips 2004, reference 1 below], [Carlsson, G. E. and Mémoli, F, JMLR 2010, cited in the paper], [Hofmeyr, David P, JMLR 2020, reference 2 below].

It is worth mentioning a connection of single-link with the concept of “Individual preference stability” studied in a recent ICML paper [3]. The connection relies on the fact that the single-link construction guarantees that the closest neighbor of each point $p$ is in the same group as $p$.  The motivations for “Individual preference stability” include guaranteeing stability in the sense that no point has the incentive to move from its group to another one and fairness (each point is “happy” with its location).  We thank referee GUvh for pointing out this reference.
 
In summary, we are contributing to extending the current knowledge regarding an important algorithm in Machine Learning, which, by itself, we believe makes our paper interesting for the Neurips community.

**Potential Applications**

We agree that our discussion on use cases for our algorithms should be expanded, as only a few lines (34-38) were dedicated to presenting a single use case (ensuring diversity in committees). 

Here we discuss two other potential use cases: ensuring population diversity in candidate solutions for genetic algorithms [4] and data diversity when training machine learning algorithms [5]. We will add this discussion to the new version of the paper.

When training a machine learning model, ensuring data diversity may be crucial for achieving good results [5]. In situations in which all available data cannot be used for training (e.g. training in the cloud with budget constraints), it is important to have a method for selecting a diverse subset of the data, and our algorithm can be used for this: to select $n = kL$ elements, one can partition the full data set into $k$ clusters, all of them containing at least $L$ members, and then select $L$ elements from each cluster. Using Single-Link to create $kL$ groups and then picking up one element per group is also a possibility but it would increase the probability of an overrepresentation of outliers in the obtained subset, as these outliers would likely be clustered as singletons (see our Figure 2 on the prevalence of singletons when using Single-Link). 

Regarding the above application, we note that, as in the case of diverse committees, our algorithm can be used to create not only one but several diverse and disjoint subsets, which might be relevant to generate partitions for cross-validation or for evaluating a model's robustness.  For that,  each subset is obtained by picking exactly one point per group.


For genetic algorithms, maintaining diversity over the iterations is important to ensure a good exploration of the search space [4]. If all candidate solutions become too similar, the algorithm will become too dependent on mutations for improvement, as the offspring of two solutions will likely be similar to its two parents; and mutation alone may not be enough to fully explore the search space. We can apply our algorithm in a similar manner as mentioned above, by partitioning, at each iteration, the solutions into $k$ clusters of minimum size $L$ and selecting the best $L$ solutions from each cluster, according to the objective function of the underlying optimization problem, to maintain the solution population simultaneously optimized and diverse. Using Single-Link could lead to several poor solutions being selected to remain in the population, in case they are clustered as singletons.

We finally note that an algorithm that optimizes intra-group measures (e.g. $k$-means or $k$-medians) would not necessarily guarantee diversity for the aforementioned applications, as points from different groups can be close to each other.


Meta-review: Though there is some variance in the opinions of reviewers, several found that the minimum size constraints formulation here is natural and novel, with a number of valuable contributions in the optimization of inter-group criteria. Moreover, the performance of the method is also promising. As some of the dismissive claims in the negative reviewers are not as clearly supported in my view, my own read tends to agree in finding value that will be of interest to the NeurIPS community.
Decision: Accept (poster)