Proportionally Representative Clustering

As artificial intelligence and machine learning serve as the ‘new electricity’ of systems, it is becoming increasingly important to ensure that AI systems embody societal values such as privacy, transparency, and fairness. Fairness is a growing concern, as AI systems are used to make decisions that can critically affect our daily lives, finances, and careers [17]. The impulse to tackle the issue of fairness in AI is prominently reflected in several governmental policy documents [18, 3, 24], the emergence of dedicated conferences on Ethical AI, and the formation of AI ethics boards by various big tech companies. Over the past years, several developments have taken place in the theory and application of fairness in supervised learning. One prominent approach is to use information derived from labelled data in supervised learning to formalize some notions of equity within and across (pre-specified and) protected attributes [21]. In contrast, in several models of unsupervised learning, protected attributes or their labelling are unknown. Fairness in unsupervised machine learning is becoming important with the growth of data collection both in public (e.g., via IoT devices) and private sectors (e.g., map services and social media). Unfettered and irresponsible use of such data has the danger of increasing inequity [37].

We focus on fairness in clustering, which is one of the most widely applied tasks in unsupervised machine learning. A (centroid selection) clustering problem has a metric space $\mathscr{X}$ with a distance measure $d:\mathscr{X}\times\mathscr{X}\rightarrow\mathbb{R}^{+}\cup\{0\}$, a multiset ${\mathscr{N}}\subseteq\mathscr{X}$ of $n$ data points (agents), a set ${\mathscr{M}}$ of candidate centers, and positive integer $k\leq n$. In many clustering problems, each data point corresponds to an individual’s attribute profile; thus, we refer to the data points as agents. The goal is to find a size-$k$ subset of centers, $Y\subseteq{\mathscr{M}}\ :\ |Y|=k$. Such centroid selection problems can be widely applied to various applications including recommender systems and data-compression. The problem also captures social planning scenarios where $k$ facility locations need to be chosen to serve a set of agents.

In such a (centroid selection) clustering problem, there are two versions of the problem. In the discrete version, the set of candidate centers ${\mathscr{M}}$ is a finite subset of $\mathscr{X}$. In the unconstrained or continuous setting, ${\mathscr{M}}=\mathscr{X}$. We first focus on the unconstrained setting as done by Micha and Shah [36]. Later we discuss how our concepts and ideas extend to the discrete setting. For a location $i$ and set of locations $S{\subseteq{\mathscr{M}}}$, we will denote $\min_{c\in S}d(i,c)$ as $d(i,S)$. Standard clustering solutions include $k$-center, $k$-medians, and $k$-means.¹¹1 The $k$-center solution outputs a subset $Y\in\arg\min_{W\subseteq{\mathscr{M}},|W|=k}\max_{i\in{\mathscr{N}}}d(i,W)$. The $k$-medians solution outputs a subset $Y\in\arg\min_{W\subseteq{\mathscr{M}},|W|=k}\sum_{i\in{\mathscr{N}}}d(i,W)$. The $k$-means solution outputs a subset $Y\in\arg\min_{W\subseteq{\mathscr{M}},|W|=k}\sum_{i\in{\mathscr{N}}}d(i,W)^{2}$. These standard objectives can be viewed as achieving some form of global welfare but are not well-suited for proportional representational and fairness concerns. The problems of computing outcomes optimising these objectives are also NP-hard [34, 4].

We seek a suitable concept for clustering that captures general fairness principles such as non-discrimination, equality of opportunity, and equality of outcome. In many applications, the data points correspond to real individuals or their positions or opinions. Such individuals may expect the clustering outcome to capture natural fairness requirements. Previous axiomatic studies of clustering have measured fair representation by the distance from each data point to the nearest centroid. We initiate a proportional representation perspective on fairness in clustering. In capturing this desiderata axiomatically, we require a property in which representation guarantees depend on the number (or proportion) of data points and how “tightly” they are clustered together.

Our perspective is motivated by applications in which groups of individuals (to which the data points correspond) may expect to receive centroid representation proportional to their size. For instance, the centroids may be citizens selected to make representative decisions on behalf of the public, as is done in a jury or a sortition panel. Similarly, computing a proportionally fair clustering is also meaningful in facility location, where the location of the facility should depend on the density and the number of people it is serving. More generally, our axioms and algorithms are well-motivated in any setting in which one may want to take a representative sample from datapoints between which a distance metric is well-defined. In this paper, we consider the following fundamental research question. What is a meaningful concept of proportional fairness in centroid clustering? Is such a concept guaranteed to be achievable?

Proportional fairness for clustering has been considered in a series of recent papers. Chen et al. [14] first proposed a proportional fairness axiom that requires that there is no set of agents of size at least $n/k$ that can find an unselected center that is “better” (i.e., located closer than the closest selected center) for each of them.

The idea of proportional fairness was further strengthened to core fairness that requires that there is no set of agents of size at least $n/k$ that can demand a more preferred location for a center [33]. One rationale for proportional fairness is explained in the following example, which was first presented by Micha and Shah [36] and then reused by Li et al. [33]. We reuse the same example. Consider a set of data points/agents. The agents are divided into 11 subsets of clusters each of which is densely clustered. One cluster of agents has size 10,000. The other 10 clusters have sizes 100 each. The big cluster is very far from the smaller clusters. The small clusters are relatively near to each other. Micha and Shah [36] and Li et al. [33] are of the view that any set of centers that satisfies a reasonable notion of proportional fairness would place 10 centers for the big cluster and 1 center serving the small clusters. Next, we point out that proportional fairness and core fairness do not necessarily satisfy this minimal requirement, which we formalize via the unanimous proportionality axiom below.

UP captures a principle which Chen et al. [14] highlighted as desirable — in their words, one which requires that “any subset of at least $r\lceil n/k\rceil$ individuals is entitled to choose $r$ centers.”³³3In the term unanimous proportionality, unanimous refers to the condition where a set of agents have the same location, and proportionality refers to the requirements that such agents get an appropriate number of centers in proportion to the number of agents. The following example shows that proportional fairness [14] does not imply Unanimous Proportionality. Similarly, it can be shown that the fairness concept proposed by Jung et al. [28] does not imply unanimous fairness.

The example above shows that there is a need to formalize new concepts in order to capture proportional representative fairness. The property should imply unanimous proportionality but should also be meaningful if no two agents/data points completely coincide in their location. One reason why the existing fairness concepts do not capture UP is that they make an implicit assumption that an agent only cares about the distance from the nearest center and not on how many centers are nearby. As discussed in the introduction, this assumption is not necessarily accurate in contexts such as data abstraction, sortition, and political representation.

In addition to capturing proportional representation in a robust sense, we would also like our axiom (and algorithms) to guarantee the existing proportional fairness concepts, at least in an approximate fashion. Since a PF outcome may not exist, Chen et al. [14] and Micha and Shah [36] studied an approximate notion of proportional fairness in the discrete and unconstrained settings, respectively.

We seek to devise an axiom which is compatible with approximate PF, and subsequently to design algorithms which satisfy our axiom while also providing good approximate guarantees with respect to PF. We close the section with an example presented by Micha and Shah [36] that shows that a PF outcome may not exist. We will use the same example to illustrate our new fairness concept in the next section.

We propose a new concept Proportionally Representative Fairness (PRF) that captures proportional representation fairness concerns. The intuition behind the concept is based on two natural principles: (1) a set of agents that is large enough deserves to have a proportional number of centers ‘near’ it, and (2) the requirement of proximity of the nearby centers to a subset of agents should also depend on how densely together the particular subset of agents are. We use these two principles to propose a new fairness concept.

PRF has the following features: it implies unanimous proportionality; it is oblivious to and does not depend on the specification of protected groups or sensitive attributes; it is robust to outliers in the data, since the fairness requirements are for groups of points that are sizable enough; and it is scale invariant to multiplication of distances (i.e., PRF outcomes are preserved if all the distances are multiplied by a constant).

Next, let us illustrate an example where proportional fairness is not achievable but one of the most natural clustering outcomes satisfies PRF.

In addition to capturing natural outcomes when PF outcomes may not exist, PRF actually guarantees a $\rho$-PF outcome for $\rho\approx 3.6$ in the unconstrained setting on general metric spaces.

Next, we highlight that the well-known $k$-means or $k$-median solutions do not necessarily satisfy PRF. Example 4 is adapted from an example by Chen et al. [14].

On face value, it is not clear whether an outcome satisfying PRF exists as similar concepts such as PF cannot always be guaranteed [36]. Secondly, even if a PRF outcome is guaranteed to exist, the complex constraints seem computationally challenging. PRF is a property that requires conditions on an exponential number of subsets of agents. For each subset of agents, it enforces representational constraints pertaining to an infinite number of neighborhood distances. Perhaps surprisingly, we show that not only is a PRF outcome guaranteed to exist, it can be computed in polynomial time.

The algorithm intuitively works as follows. Firstly, instead of considering infinite possible centers, we restrict our attention to the $n$ candidates centers that coincide with each agent’s location. Each agent is given an initial weight of 1. This weight dynamically decreases over the course of the algorithm. The algorithm can be viewed as gradually expanding the neighborhoods of each of the agents.⁴⁴4The idea of expanding neighborhoods is used in other algorithms in the literature, such as the Greedy Capture algorithm for the unconstrained setting studied by  Micha and Shah [36]. Unlike our algorithm, it does not involve reweighting of agents. More importantly, Greedy Capture does not satisfy PRF and is not polynomial time. Our algorithm uses reweighting of agents as is done by EAR for multi-winner voting [7]. Our algorithm can be viewed as using key ideas from the EAR for committee voting while taking into account additional spatial information to make synchronized decisions. Instead of continuously expanding the neighborhood, we only consider at most $n^{2}$ possible values of neighborhood radii. If there exists some location in the candidate set such that it is in the intersection of the neighborhoods of a group of agents with total weight of at least $n/k$, we select one such candidate, and reduce the agents’ collective weight by $n/k$.⁵⁵5We point out that the reweighting process can be done in any manner that results in the group’s total weight reducing by $n/k$. Two natural possibilities would be (i) reducing weights as equally as possible, or (ii) reducing weights proportional to agent distances from the selected candidate. The process is continued until $k$ centers are chosen. The algorithm is formally specified as Algorithm 1. The following is the main result of the present section and summarizes the theoretical guarantees of Algorithm 1.

We will now formally prove two key lemmas used to prove Theorem 1.

Lemma 1 implies guaranteed existence of an outcome satisfying our axiom, which was one of our goals in devising PRF. In conjunction with Proposition 1, the lemma also gives us that the outcome returned by Algorithm 1 is $\frac{1}{2}(3+\sqrt{17})$-PF. This is noteworthy as it establishes Algorithm 1 as the first known polynomial-time approximation algorithm for PF on general metric spaces in the unconstrained setting. As we will show next, Algorithm 1 actually provides the stronger guarantee of $3$-PF.

We presented PRF as a desirable concept for the unconstrained setting. It is not immediate how to adapt the concept to the discrete setting. Applying the unconstrained PRF definition to the discrete setting leads to the issues of non-existence. On the other hand, some natural attempts to account for the coarseness of the candidate space, ${\mathscr{M}}$, can lead to a concept that is too weak. For example, one alternative is to require that an outcome $X$ be such that if, for any set of agents $S\subseteq{\mathscr{N}}$ of size at least $|S|\geq\ell n/k$ such that the maximum distance between pairs of agents in $S$ is $y$, the following holds: $|c\in X\mathbin{:}\exists i\in S\text{ s.t }d(i,c)\leq y|\geq\min\{\ell,|\cup_{j\in S}B_{y}(j)\cap{\mathscr{M}}|\}$, where $B_{r}(i)$ denote a ball of radius $r$ around agent $i$. Alternatively, we could replace the right-hand side of the final inequality with $\min\{\ell,|\cap_{i\in S}B_{y}(i)\cap{\mathscr{M}}|\}$. Both of these versions are too weak. To see this, suppose $k=1$, all agents are located at $0$, and ${\mathscr{M}}=(\ldots,-2,-1,1,2,3,\ldots)$, then neither version places any restriction on the facility location and do not even imply UP.

To resolve these issues, we need to take into account that the nearest candidate locations may be very far from a subset of agents. We adapt our PRF concept for the discrete setting via a careful adaptation of the PRF concept for the unconstrained setting.

We begin by highlighting the fact that, in the discrete setting, PRF implies $(1+\sqrt{2})$-approximate PF, the closest PF approximation known to exist in the discrete setting [14]. Our proof follows similarly to Theorem 1 from Chen et al. [14].

For the discrete setting, we propose a new algorithm (Algorithm 2). Algorithm 2 is similar to Algorithm 1, which was designed for the unconstrained setting. In fact, Algorithm 1 can be viewed as first setting ${\mathscr{M}}$ to the multiset of candidate locations corresponding to agents in ${\mathscr{N}}$ and then running Algorithm 2. Similar to Algorithm 1, Algorithm 2 terminates in polynomial time and returns $k$ centers and its output satisfies PRF.

Notably, by satisfying PRF, Algorithm 2 matches the best known PF approximation factor in the discrete setting. As the following remark highlights, however, the existing algorithms do not capture PRF.

In F, we experimentally compare Algorithm 2 to ALG_g and a variant of k-means. We show that it performs especially well when the mean squared distance of the agents is calculated based on their distance from not only the closest center but also the next $j$-closest centers (for large $j$). This provides another perspective indicating that, in situations where a “fair” clustering should account for an agent’s distance from more than just her closest center, our algorithm is better suited than the existing alternatives. In C, we consider two natural and stronger notions of PRF in the discrete setting (that also apply to the continuous setting). We show that the versions that we consider do not guarantee the existence of a fair outcome.

We revisited a classical AI problem with a novel solution concept that builds on ideas from social choice and fair division. We proposed a natural fairness concept called PRF for clustering. PRF is guaranteed to exist and has desirable features: it implies unanimous proportionality, does not require the specification of protected groups, and is robust to outliers and multiplicative scaling. Even if our only focus is on the PF axiom, we make significant progress on efficient algorithms for approximate PF for general metric spaces. We did not focus on strategic aspects. Unfortunately, PRF and PF are incompatible in general with the incentive of an agent to report their location truthfully (see E). A natural next step is to identify stronger versions of PRF that still guarantee existence. It will be interesting to consider refinements of our algorithms which make more clever choices when selecting candidates with sufficient weighted support. Another direction for future research is to understand how much impact the constraint of PRF imposes on standard optimization objectives such as for $k$-means, $k$-median, or $k$-center.

Haris Aziz is supported by the NSF-CSIRO project on “Fair Sequential Collective Decision-Making”. We thank John Dickerson and Bo Li for helpful comments.