Fair AI/ML 5 PROP in Non-Centroid Clustering
Read the paper Proportional Fairness in Non-Centroid Clustering by Caragiannis et al.
This paper was accepted in NeurIPS 2024!
Introduction
points, clusters , distance metric .
-means objective: .
Scenario in which there are no cluster centers.
Question:
- Can we obtain PROP guarantee for non-centroid clustering?
- Do the algorithms for centroid clustering also work for non-centroid one?
- Can we audit the PROP of a given algorithm?
Contribution
Each agent has a loss function , the loss under clustering is . denotes the cluster containing her.
- can be arbitrary
- can be distance
PROP fairness guarantee:
- the core
- and its relaxation, fully justified representation FJR.
Summary of results
Loss functions | Core UB | Core LB | FJR |
---|---|---|---|
Arbitrary | |||
Average | polytime | ( in polytime) | |
Maximum | polytime | ( in polytime) |
FJR as a relaxation of the core. This paper propose GreedyCohesiveClustering
, which is an adaptation of Greedy Cohesive Rule from social choice theory.
Related Work
PROP by Chen et al.
PROP revisit by Micha and Shah
FJR in centroid clustering by Aziz et al.
Model
for . Given a set of agents, and the desired number of clusters .
Each agent has an associated loss function , where is the cost to agent for being part of group . A -clustering is a partition of into clusters, where for and . For simplicity, is the cluster containing .
The loss of is .
Loss function
- A distance metric over is given by , which satisfies normality, symmetry and triangle inequality.
- Arbitrary losses. The loss is arbitrary non-negative number for each agent and cluster .
- Average loss. Given a distance metric over , for each agent and cluster . Agent prefers the agents in her cluster to be close to her on average.
- Maximum loss. Given a distance metric , . Agent prefers that no agent in her cluster to be too far from her.
Core
If no group of agents can choose another outcome that
- They are entitled to choose based on their proportion of the whole population
- Every member of group is happier
📖Definition 1 (-Core). For , a -clustering is said to be in the -core if there is no group of agents with s.t. for all . -core is the core.
If a group exists that becomes a violation of the -core guarantee, we say that it deviates and refer to it as the deviating coalition.
🎯Theorem 1. For arbitrary losses, there exists an instance in which no -core clustering for any finite .
🎯Theorem 2. For the average loss, there exists an instance in which no -core clustering exists an instance in which no -core clustering exists for .
❓Open problem 1: For the maximum loss, does there always exist a clustering in the core?
❓Open problem 2: For the average loss, does there always exist a clustering in the -core for some constant ?
GreedyCohesiveClustering Algorithm
It uses a subroutine , in which given a subset of agents , metric , and threshold , finds a cohesive cluster .
The threshold indicate the smallest size at which a group of agents deserve to form a cluster.
is SmallestAgentBall. It finds the smallest ball centered at agent that captures at least agents, and returns a set of agents from this ball.
- Natural choice:
So GreedyCohesiveClustering with SmallestAgentBall iteratively finds the smallest agent-centered ball containing agents and removes in that ball, until fewer than agents remain, at which point all remaining agents are put into one cluster and any remaining clusters are left empty.
Pseudo code for GreedyCohesiveClustering
Input:
Output: -clustering
- // remaining set of agents
- // current cluster member
- while do
- // find and remove the next cohesive cluster
- return
Pseudo code for SmallestAgentBall
Input: Subset of agent
Output: a cluster
- if then return
- if do
- -th closest agent in to agent // arbitrarily broke the tie
- // smallest ball centered at agent capturing at least agents
- return the set of closest agents in to agent
Actually the GreedyCohesiveClustering is an adaptation of Greedy Capture by Chen et al. There are two key difference:
- Growing balls centered at the agents instead of all feasible candidate centers.
- Stop a ball as soon as it captures agents. While in GC, it continues.
🎯Theorem 3. For the average (resp. maximum) loss, the Greedy Capture algorithm is guaranteed to return a clustering in the -core (resp. -core) in time complexity, and the bounds are tight.
Fully Justified Representation
Peters et al. introduced FJR as a relaxation of the core in the context of approval-based committee selection.
📖 Definition 2 (-FJR). For , a -clustering satisfies -FJR if there is no group of agents with s.t. for each , i.e., if . We refer to -FJR as FJR.
🤔Proposition 1. For , -core implies -FJR for arbitrary loss functions.
Trivially, .
Arbitrary Loss Functions
FJR clustering is guaranteed to exist even for arbitrary losses.
📖Definition 3 (most cohesive cluster). Given a set of agents and a threshold , the MostChesiveCluster problem asks to find a cluster of size at least s.t. the maximum loss of any for is minimized, i.e., find .
For , a -approximate solution satisfies for all with , and a -approx algorithm returns a -approx solution on every instance.
If we plug in to the MostCohesiveCluster problem into GreedyCohesiveClustering algorithm yields -FJR clustering.
🎯Theorem 4. For arbitrary losses, , and an -approximation algorithm for the MostCohesiveCluster problem, GreeedyCohesiveClustering is guaranteed to return a -FJR clustering. Hence, FJR is guaranteed to exist.
Proof omitted.
Average and Maximum Loss Functions
Let be an exact ALG for the MostCohesiveCluster problem for the average loss.
It may run not in polynomial time. It can be used to detect whether a given undirected graph admits a clique of at least a given size (NP-Complete).
🤔Lemma 1. For the average (resp. maximum) loss, SmallestAgentBall is a -approximation (resp. -approximation) algorithm for the MostCohesiveCluster problem, and this is tight.
🤔Corollary 1. The Greedy Capture algorithm is guaranteed to return a clustering that is -FJR (resp. -FJR) for the average (resp. maximum) loss.
❓Open problem 3: For the average or maximum loss, what is the smallest for which an -FJR clustering can be computed in polynomial time, assuming ?
❓Open problem 4: What is the smallest s.t. there always exists a clustering that is simultaneously -FJR for both the average loss and the maximum loss?
Auditing FJR
Ideas used to find an approx FJR can also be used to audit the FJR approx of any given clustering.
📖Definition 4 (-approx FJR auditing). is a -approx FJR auditing algorithm, if given any clustering , it returns s.t. the exact FJR approx of is in .
🎯Theorem 5. For , if is a -approx algorithm to the MostCohesiveCluster problem, then AuditFJR is a -approx FJR auditing algorithm. Given lemma 1, it follows that for the average (resp. maximum) loss, AuditFJR(SmallestAgentBall) is an efficient -approx (resp. -approx) FJR auditing algorithm.
❓Open problem 5: Does there exist a polynomial time, -approx core auditing algorithm for some constant ?
🎯Theorem 6. Assuming , there does not exist a polynomial-time -approx FJR auditing algorithm for the maximum loss, for any ,
Experiments
Omitted
Discussion
Introduction to Proportional Fairness in Non-Centroid Clustering: This paper initiates the study of proportional fairness in non-centroid clustering and presents several open questions for further exploration.
Key Open Questions:
- Achieving a better approximation than for the core concerning average loss.
- Determining if the core is always non-empty for maximum loss.
Core Non-Emptiness Results:
- Proven that the core is always non-empty for maximum loss in 1-dimensional metric spaces (Appendix C.1).
- For average loss, however, the core remains empty even on the line (Appendix C.2).
Differences Between Clustering Settings:
- Highlights significant distinctions between centroid and non-centroid clustering.
Future Directions:
- Investigate proportional fairness guarantees when an agent’s loss depends on both their cluster center and other agents in their cluster.
- Explore the possibility of intrinsically choosing the number of clusters , which currently requires being fixed in advance for proportional fairness.
Compatibility with Classical Algorithms:
- While traditional algorithms like -means and -centers may be incompatible with the core and FJR (Appendix E), studying conditions under which they might align with fairness criteria or can be efficiently computed is an interesting avenue.