Unifying Proportional Fairness in Centroid and Non-Centroid Clustering

Thank you for your detailed and helpful review.

Comments:

• Equivalence between two forms of k-means: We agree that this phrasing was misleading. We meant to provide only an example setting (where $\mathcal{M}$ is the entire Euclidean space and $d = L_2$) in which the "centroid" and "non-centroid" k-means become equivalent. We will clarify this detail in the camera ready version.

• Regarding proportionality principle wording: We agree with your comment and will revise this as: "which is a principle inspired from the democratic ideal of proportional representation that aims to give groups influence proportional to their size and cohesion."

• We will also make the changes to the references and the stylistic changes you suggested.

• Regarding experiments: As we mentioned to Reviewer wHCe, we will update Section 1.1 in the camera-ready version to include a more detailed synopsis of our empirical findings.

Questions:

Q1: Motivation for semi-centroid clustering: Please see our responses to Reviewer wHCe's Q1, SNW3's Q1, and sbW8's Q3. In Section 6, we discuss motivating applications such as assigning students to group projects and scheduling talks of papers accepted to a conference, where both non-centroid and centroid losses matter simultaneously.

Quoting from our response to Reviewer SNW3:

One such application is assigning students to groups for a class project. In this setting, the agents would be the students, and the centroids would be project topics. The non-centroid metric space would represent the friendships of the students, while the centroid metric would represent students' preferences over project topics. It may be impossible to embed both these preferences in a single metric space, as we may have two students who are very close friends, but have very different preferences over project topics. The dual metric model allows us to take this into account and find a grouping of the students that balances placing friends in the same group with assigning students to topics of their liking.

For scheduling talks of papers accepted to a conference, the non-centroid loss would model the (dis)similarity between two papers, while the centroid loss would model the (ir)relevance of a session's title to a paper in that session.

While there are several real-world applications where agents are grouped into clusters and each cluster is assigned a "centroid", coming to your question, we are not aware of any technical papers or settings studied in prior work that model both the non-centroid and centroid aspects simultaneously. This speaks to the conceptual novelty of our work.

Q2: The case of $\mathcal{M}=\mathcal{N}$. This is an extremely interesting question. Due to space constraints, we were only able to allude to this special case in the Discussion (see line 366).

For the dual metric setting, Algorithm 1 with $\mathcal{M}=\mathcal{N}$ indeed does not guarantee that the centroid for each cluster will be an agent from that cluster because the MCC computed at a step may select a centroid from outside the cluster. It is easy to see that this is inevitable if one wishes to prevent clusters of the form $(C,x)$ with $x \notin C$ from deviating and significantly improving. However, if the desideratum is weakened to approximate core against only deviating clusters $(C,x)$ that satisfy $x \in C$, we do not know if it can be achieved for the dual metric setting.

However, whenever $\mathcal{M} = \mathcal{N}$, it is presumable that both centroid and non-centroid losses are represented by the same metric, meaning that we are in the case of weighted single metric loss. Here, it is worth noting that one of our algorithms, Algorithm 5, naturally achieves your desideratum: Algorithm 5 simply runs non-centroid GreedyCapture (where balls grow around the agents) and then assigns each cluster the centroid closest to the agent $i \in C$ at the center of the ball that captured the cluster. When $\mathcal{M} = \mathcal{N}$, we are guaranteed to have $x=i$ WLOG, meaning that the centroid will always be an agent in the cluster. Algorithm 5 gets a core approximation of $\frac{2}{\lambda}$, which is reasonable for all lambda values that are not too close to 0.

That said, Algorithm 6, which allows us to achieve finite core approximation for the regime of $\lambda$ close to $0$ under weighted single metric loss, does not always select a centroid from within the cluster. Whether this can be enforced remains an interesting open question.

We will add this discussion to Section 6.

Thank you for your detailed review.

Q1: Best factor for centroid or non-centroid clustering. The approximation guarantees of Algorithm 1 are closely controlled by the growth factor $c$. Recall that $c$ dictates how much an agent $i$ is allowed to hurt the losses of other agents when switching into their cluster for its own benefit during Phase 2 of the algorithm.

Theorem 2 indicates that setting $c=3/2$ can already recover $3$-core guarantee for each of centroid and non-centroid clustering (by setting the other distance metric as $0$). However, setting different values of $c$ can recover optimized guarantees in each setting from prior work.

Specifically, when we set $c=0$, agents will not be allowed to switch away from their original cluster if it hurts the agents in that cluster at all. This essentially means that Phase 2 of the algorithm will be skipped, and Algorithm 1 will roughly mimic the behaviour of the non-centroid GreedyCapture of Caragiannis et al. [2024] to achieve $2$-core for non-centroid clustering. Similarly, if we set $c=\infty$ (formally, if in Phase 2 we say that every agent can simply switch to its favourite cluster, regardless of the loss it causes other agents), then the algorithm would mimic the centroid GreedyCapture of Chen et al. [2019] to achieve $(1+\sqrt{2})$-core for centroid clustering.

With these respective growth factors, the only difference between our Phase 1 and the GreedyCapture algorithms for these settings is that Algorithm 1 finds the Most Cohesive Cluster at each step rather than finding the clusters by growing a ball around each agent or cluster center. By analyzing the original greedy capture proofs in both settings, it is easy to see this difference does not impact any of the guarantees.

Q2: Extending non-centroid clustering to semi-centroid clustering. That's a great question. The answer is no. This follows from the fact that the non-centroid GreedyCapture of Caragiannis et al. [2024] computes a balanced clustering (where each cluster is of size at most $\lceil n/k \rceil$) in the 2-core (i.e., $\alpha=2$ in your question). However, in Appendix F, we show that there are instances of semi-centroid clustering in which every balanced clustering has core approximation at least $1/\sqrt{\lambda}$. Hence, when $\lambda = o(1)$, one cannot guarantee a constant $\beta$ in your question.

Q3: Motivation: Indeed, we will expand our federated learning motivation to explain the setup more in detail. That said, our goal was to demonstrate that the motivations used by prior work for centroid and non-centroid clustering may already involve at least a slight semi-centroid consideration. We discuss new motivating examples in Section 6 that more directly align with semi-centroid clustering, which we plan to discuss early in Section 1 in the camera-ready version (see also our responses to Reviewer wHCe's Q1 and SNW3's Q1).

Thank you for your review.

Regarding the example in Theorem 1: Indeed, the counterexample used to prove Theorem 1 is insightful as we later reuse it to prove Theorems 5 and 9 too. We'll be happy to add it to the main body.

Plot of upper and lower bounds: This is a great idea. We will be happy to add such a plot to the main body.

Q1: Motivation for two different metrics. There are several scenarios where having different metrics can be helpful. We briefly describe the motivation in Section 6, but agree that this belongs to the introduction and will move it there in the camera-ready version.

One such application is assigning students to groups for a class project. In this setting, the agents would be the students, and the centroids would be project topics. The non-centroid metric space would represent the friendships of the students, while the centroid metric would represent students' preferences over project topics. It may be impossible to embed both these preferences in a single metric space, as we may have two students who are very close friends, but have very different preferences over project topics. The dual metric model allows us to take this into account and find a grouping of the students that balances placing friends in the same group with assigning students to topics of their liking.

Thank you for your detailed and helpful review.

We will fix the typos you found and simplify the presentation of Algorithm 1 in the camera-ready version of the paper.

Regarding experiments: While we would have liked to include them in the main body, we were restricted by the page length. In the camera-ready version, we will significantly expand on the paragraph in Section 1.1 that mentions the experiments to include a summary of our key findings.

To address your questions:

Q1: Choosing $\lambda$, metric, and MCC approximation.

Choosing $\lambda$: In real-world scenarios, the correct value of $\lambda$ would likely be very context dependent. For example, when clustering conference papers into sessions, it is presumable that the non-centroid loss (similarity between papers presented in the same session) matters significantly more than the centroid loss (relevance of a session's title to a paper in that session), leading the conference chair to select $\lambda$ close to $1$. However, when clustering students for group projects, the centroid loss (how much a student prefers to work on a given project idea) may matter just as much as the non-centroid loss (how much two students like working with each other), leading the educator to select a more intermediate value of $\lambda$. In general, the practitioner would use their insight as to which factor matters more (or if they both matter equally) and choose $\lambda$ to reflect that. (See also our response to Reviewer SNW3's question.)

Choosing the metric(s): There are two ways to understand your comment about sensitivity to the choice of the metric(s).

1. What if a practitioner feeds slightly distorted metrics $\hat{d}^c$ and $\hat{d}^m$ that are at most a $1+\epsilon$ (multiplicative) factor off from the true $d^c$ and $d^m$ in measuring any pairwise distance? In this case, we have checked that all our approximation guarantees scale gracefully in $\epsilon$. The distortion factor just carries through all the equations. If the reviewers feel that this would be helpful, we will be happy to add formal robustness results in the appendix of the camera-ready version.

2. Could the approximation factors improve for specific choices of $d^c$ and $d^m$? Prior work of Micha and Shah [2020] shows that for centroid clustering, the core approximation of GreedyCapture improves under the $L_2$ distance in a Euclidean space. It would not be surprising if the same holds in our semi-centroid setting. This would require novel arguments and is left to future work.

Choosing MCC approximation factor: For our algorithms, an $\alpha$ approximation of MCC smoothly translates to an $\alpha$ approximation of FJR and a $\frac{1}{2}(1+\sqrt{\alpha(\alpha+8)}+2)$ approximation of the core (see Theorem 6 and Lemma 1, respectively). That said, a practitioner would likely only choose one of two values: $\alpha=1$, if running time is not a concern and the practitioner is willing to solve a simple MILP with $O(|N|+|M|)$ variables and constraints to find a $1$-MCC cluster, and $\alpha=4$, if polynomial running time is a concern and the practitioner wishes to use Algorithm 7.

Q2: running time. With $n=|N|$ and $m=|M|$ (and noting that $k \le n$), a simple implementation of GreedyCapture runs in $O(n m \log (nm))$ time. Algorithm 4 for computing a $4$-MCC cluster runs GreedyCapture $m$ times, meaning Phase 1 of Algorithm 1 runs in $O(n m^2 \log (nm))$ time. Phase 2 of Algorithm 1 runs in $O(n^2)$ time. This puts the overall runtime of Algorithm 1 at $O(n m^2 \log (nm))$. Our algorithms for the single-metric setting have similar runtimes. Algorithms 5 and 6 both rely on greedy capture and can be implemented in $O(n^2 \log n + km)$ and $O(n m \log (nm) + kn)$ time, respectively. We will add these details in the camera-ready version.

Empirically, we observed that our algorithms are slower than k-means and k-medoids. As an example, the table below shows the runtimes (in seconds) of Algorithm 6, k-means and k-medoids on the Adult dataset subsampled to different sizes, fixing the default values of $k=15$ and $\lambda=0.5$. Please see the Appendix E for details of the experimental setup and implementation. Designing faster (perhaps even near-linear time) algorithms with provable proportional representation guarantees remains an exciting open question for future research.

Q3: general losses. For arbitrary loss functions, the core remains inapproximable to any finite degree, even in non-centroid clustering [Caragiannis et al., 2024], whereas (exact) FJR remains feasible (Theorem 6). An interesting future direction would be to find families of loss functions that are more general than our dual metric loss, but still allow a reasonable approximation of the core.