Optimization of Inter-group Criteria for Clustering with Minimum Size Constraints

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. At 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. Moving 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.

Strengths

1) The paper is technically solid and well-written. 2) The inter-clustering objective is cute and quite novel. From the theoretical perspective it opens up a new direction for clustering research. 3) 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. If it wasn't for the lack of motivation my score would most likely be higher.

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. https://arxiv.org/abs/2006.04960 https://arxiv.org/abs/2207.03600 2) 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.

Rating

8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

4 excellent

Presentation

3 good

Contribution

3 good

Limitations

N/A

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.

Strengths

* The paper is well-written * The problem is interesting from a theoretical perspective * 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. * 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? * 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?

Questions

* What is another example application other than the diversity example given on lines 34-38? * What benefits do Min-Sp and MST-Sp have over other clustering objectives? Why would a user choose this objective over another objective? * How might one select the minimum cluster size? Could this be an issue just as difficult as selecting the number of clusters $k$?

Rating

3: Reject: For instance, a paper with technical flaws, weak evaluation, inadequate reproducibility and incompletely addressed ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

3 good

Contribution

2 fair

Limitations

Limitations are adequately addressed.

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). However, 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.

Strengths

1. Introduce an interesting problem. 2. 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$. 1. 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. 2. 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.

Questions

1. It is not clear if the problems are non-trivial or follow from known ideas/techniques. 2. Please explain if instead of placing lower bound of $L$, placing an upper bound of $L$ will change the problem significantly.

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

2 fair

Presentation

2 fair

Contribution

2 fair

Limitations

No negative impact.

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). The 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. The 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). The paper concludes with some experiments documenting the performance of their proposed algorithms.

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. The paper is also, subject to some technical knowledge, clear and easy to follow.

Weaknesses

Nothing substantial. Arguably some missed pieces of literature: - 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. - 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. - Maximum Margin Clustering: Xu, Linli, James Neufeld, Bryce Larson, and Dale Schuurmans. "Maximum margin clustering." Advances in neural information processing systems 17 (2004). Typos and similar: - Line 111: plural of vertex is "vertices" - Lines 126-7: "the the cut property... and the cut property"??? - Include the explicit version of PTAS

Questions

None which I can think of. Good work

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

4 excellent

Presentation

3 good

Contribution

3 good

Limitations

None noted

Adjustment of my score

I have read all reviews and all rebuttals. Based on that I decided to update my score to an 8 (Strong Accept). Here are the reasons for this adjustment: 1. My only concern about the paper when I first read it, was the lack of motivation. I am satisfied with the example that the authors gave in their rebuttal and I encourage them to include it in the main paper. 2. I do not agree with reviewer FsJN saying that this paper/problem is of no interest for the NeurIPS community. I can honestly attach a 50+ list of papers on clustering from NeurIPS/ICML/AAAI/AISTATS/etc that are of a more algorithmic/theoretical flavor, yet they have been published in these venues, have been accepted by the community and some of them have even sparked new and exciting research directions (the seminal "Fair Clustering Through Fairlets" is the first example that comes to mind). 3. I do not agree with reviewer FmRy saying that the results presented in the paper are trivial. For one thing the authors did a great job refuting the claim for the two "simpler" solutions the reviewer proposed. In addition, even though the algorithms are relatively simple and use some known techniques (clearly every clustering algorithm that has a minmax distance objective will first guess the optimal value), in my opinion there's ingenuity in the proofs. Overall, I believe that it would be a pity if this paper is not accepted at NeurIPS.