Proportional Fairness in Non-Centroid Clustering

Summary

The papers study two notions of proportional fairness in clustering, namely: 1) The core as introduced by Chen et al. 2) Fully Justified Representation (FJR), which is a relaxation of the above and was introduced by Peters et al. The novelty of the paper lies in studying these problems in clustering setting that you are not required to choose clusters centers. In that context the authors start by formally defining the clustering objectives. In the case of the core, they show that arbitrary objectives are not tractable, and that an adaptation of the Chen et al. algorithm can achieve satisfactory approximation results (for the average and maximum objectives). For FJR they show a cute reduction to choose-a-single-cluster problem, and by plugging in this algorithm to the Chen et al. one they once again achieve strong approximation results. This reduction even produces results for arbitrary objective functions.

Strengths

1) Studying notions of fairness in a non-centroid context makes a lot of sense from a practical perspective 2) The paper is very well-written and easy to follow. 3) The theoretical results are sound and properly accompanied by an experimental evaluation.

Weaknesses

The techniques are not particularly novel, but I don't think that's a major weakness.

Questions

Some of you non-centroid objectives remind me of Single-Link HC clustering (see Optimization of Inter-group Criteria for Clustering with Minimum Size Constraints for example). Do you think that these algorithms could be easily adapted for proportional fairness?

Rating

8

Confidence

4

Soundness

4

Presentation

4

Contribution

3

Limitations

N/A

Summary

This paper studies proportionally fair non-centroid clustering under the fairness criteria core and fully justified representation (FJR). Both notions are well-studied in the context of centroid clustering. However, the authors claim that they are the first to consider them in the non-centroid setting. They study the fairness criteria of the core and FJR and approximations to them under different agent-based loss functions - arbitrary (non-negative) losses - average loss (average distance of an agent to the other agents in her cluster) - maximum loss (maximum distance of an agent to the other agents in her cluster) An $\alpha$-approximation to the core (or $\alpha$-core) is defined as a clustering where no entitled group of agents would want to deviate to a new coalition unless the loss of any agent in the new coalition would be at most an alpha-fraction of the former cost. For the core under arbitrary loss functions, they prove approximation hardness for any constant factor. Even for the case of average loss, they show that there is no constant-factor approximation better than $(1+\sqrt{3})/2$. On a positive side, they constructively show existence of a clustering in the O(n/k)-core under the average loss function and existence of a clustering in the 2-core under maximum loss. If the metric space is 1-dimensional, they can even prove existence of a clustering in the 1-core under maximum loss. An alpha-FJR clustering requires that no eligible group of agents would want to deviate unless every agent in the new coalition would have at most an $\alpha$-fraction of the loss of the agent with the least initial loss. They start by constructively showing existence of FJR clusterings using the slow GreedyCohesiveClustering algorithm. To achieve polynomial-time running times they give the faster GreedyCapture algorithm that, using the SmallestAgentBall subroutine, achieves 4-FJR for average loss and 2-FJR for maximum loss simultaneously. Finally, they give an auditing algorithm (AuditFJR) which returns an estimate of the approximation ratio. Plugging in the right subroutine, they get approximation factors of 4 for average loss and 2 for maximum loss. They complement this by showing hardness of approximation beyond a factor of 2 for FJR auditing under maximum loss. In a practical evaluation, they compare the efficient GreedyCapture algorithm with k-means++ and k-medoids on real data under the objective values of average within-cluster distance, k-means, and k-medoids. Their experiments reveal that the actual FJR approximation of GreedyCapture is close to 1 in practice. Further, for any of the objective functions under consideration, they find that GreedyCapture yields values at most twice that of k-means++ and k-medoids, respectively.

Strengths

The paper studies an interesting set of problems and the authors claim to be the first to study the fairness criteria core and FJR for non-centroid clustering. From this point of view, it is interesting to see that the methods from centroid-clustering translate nicely to the non-centroid setting. They achieve good approximation factors for FJR. In practice, their deterministic polynomial-time algorithm GreedyCapture even beats these approximation factors (the actual approximation factor stays close to 1 on the considered real data). Overall, the paper is nicely written and well understandable.

Weaknesses

The proposed algorithms are only slight adaptations from an algorithm proposed in [1], which was formulated for centroid clustering. It would be interesting to see whether one can think of novel approaches leveraging properties characteristic for the non-centroid setting. _Typos_ - line 53: "clsutering" - line 207: missing dashes around $S$ - line 215: right side of the inequality: $l_i$ instead of $\lambda_i$ _Small Remark_ I think it would enhance readability if you restate the theorems you prove in the appendix.

Questions

- definition of the $\lambda$-approximate solution in lines 215-216: should the $\lambda$ not be on the other side of the inequality? - do your results hold for general metric spaces or only for Euclidean metric spaces? Please write this more clearly. - what is the notion of dimension here? - what is the formal definition of core/FJR violation?

Rating

7

Confidence

4

Soundness

3

Presentation

3

Contribution

3

Limitations

The authors discuss limitations of their work by providing a comprehensive list of open problems.

Summary

This paper considers the proportional fair clustering for the non-centroid clustering. They consider three types of clustering loss for each agent in a cluster: arbitrary loss, average loss, and maximum loss. The average (maximum) loss is the average (resp. maximum) distance from this agent to other agents in the cluster. They first consider the alpha-core for proportional fairness, which requires a clustering such that no group with size at least n/k satisfies every agent in the group has a loss at most the current loss divided by alpha. For arbitrary cost, they show an instance in which there is no alpha core clustering for any finite alpha. For average loss, they show a 1.366 lower bound and provide an O(n/k)-core clustering algorithm. For maximum loss, they show a 2-core clustering algorithm. Then, they consider a relaxation of the core clustering, fully justified representation (FJR). It only requires the clustering satisfies there is no group with size at least n/k such that every agent in the group has a loss at most the minimum loss in its current cluster divided by alpha. They first show that for arbitrary loss, there exists a 1-FJR clustering. Then, they show an efficient algorithm that finds 4-FJR and 2-FJR for average loss and maximum loss respectively. They also show an efficient 4-approximation and 2-approximation FJR auditing algorithm for average loss and maximum loss.

Strengths

1. The paper is well-written and easy to follow. 2. The paper extends the proportional fairness to non-centroid clustering, which is reasonable and interesting. They provide interesting algorithms that achieve approximation for the core clustering and the FJR clustering. 3. Their algorithm and analysis can potentially be used for other clustering problems.

Weaknesses

Minor: Line 215: lambda_i(S’) should be l_i(S’).

Questions

-

Rating

7

Confidence

4

Soundness

3

Presentation

3

Contribution

3

Limitations

Yes, they mentioned the limitations.

Summary

This paper considers the proportional fairness in non-centroid clustering, where the loss of an agent is a function of the other agents in its cluster. It is the first work to study the proportional fairness guarantee in non-centroid clustering. It is interesting to consider the non-centroid clustering under the core and its relaxation. For the non-centroid clustering, authors study three different loss functions including arbitrary loss, average loss and maximum loss, respectively. For arbitrary loss, authors prove that no finite approximation of the core can be guaranteed. For the average and maximum loss, authors present a greedy capture algorithm that achieve $O(n/k)$-core and 2-core in $O(nk)$ time, respectively. The greedy capture algorithm is an adaptation of the algorithm developed for the centroid clustering under proportional fairness constraints. Additionally, for the fully justified representation (FJR), which is the relaxation of the core, authors provide constant approximations returned by the greedy capture algorithm. Moreover, authors turn to auditing the FJR approximation of a given clustering, and show that the used same technique achieves a constant approximation of FJR, which can be used to estimate the FJR approximation of any given clustering, up to a constant factor. Experiments on real data show that traditional clustering algorithms are highly unfair, whereas the greedy capture algorithm is considerably fairer and incurs only a modest loss in common clustering objectives.

Strengths

1.This paper introduces the non-centroid clustering under two proportional fairness criteria, i.e., the core and its relaxation, and provide some approximation algorithms. 2.For the FJR, the approximation results show that while it is a slight relaxation of the core, it is satisfiable even under arbitrary loss functions, whereas the core can be unsatisfiable even under more structured loss functions.

Weaknesses

1.For the average loss, the $O(n/k)$-core loss returned by the greedy capture algorithm is large, compared with the 2-core of the maximum loss. 2. The practical background of the non-centroid clustering under proportional fairness constraints is unknown. And, it is unfair that in experiments, authors compare the proposed algorithms with $k$-means++ and k-medoids, which cannot obtain solutions satisfying proportional fairness. 3. The running time of algorithm is not compared in experiments, and the datasets have small sizes.

Questions

Q1: As the authors mentioned, in other applications of clustering, i.e., federated learning, there are no “cluster centers”. What is the practical background in studying the non-centroid clustering of fairness? Q2: The authors give the first work studying the proportional fairness in non-centroid clustering. Is it fair to compare the proposed method with centroid-based methods, i.e., $k$-means++, in experiments? Therefore, the experimental result shown in Figure 1 is normal, in which the greedy capture method is significantly better than both $k$-means++ and k-medoids for the Census Income dataset. Q3: As the authors mentioned, the proposed algorithm of this paper is an adaptation of the algorithm developed for the centroid clustering in [1]. The technique used in this paper is similar to that of [1], with a slight difference in stopping a ball as soon as it captures $n/k$ agents. What are the technical novelties of this paper? Please highlight it. Q4: Why not compare the running time of algorithms in experiments? Why the experiments are conducted on smaller datasets? Is it possible to test on larger datasets, e.g., millions or even hundreds of millions? Q5: The one of the main results of this paper is an $O(n/k)$-core for the average loss by the proposed greedy capture algorithm. Can the $O(n/k)$-core be improved using other technique?

Rating

6

Confidence

4

Soundness

3

Presentation

2

Contribution

2

Limitations

The broader impacts have been discussed in the last paragraph of the paper and I don’t expect any negative societal impacts for the proposed methods.