We consider the problem of spectral clustering under group fairness
constraints, where samples from each sensitive group are approximately
proportionally represented in each cluster. Traditional fair spectral
clustering (FSC) methods consist of two consecutive stages, i.e., performing
fair spectral embedding on a given graph and conducting $k$means to obtain
discrete cluster labels. However, in practice, the graph is usually unknown,
and we need to construct the underlying graph from potentially noisy data, the
quality of which inevitably affects subsequent fair clustering performance.
Furthermore, performing FSC through separate steps breaks the connections among
these steps, leading to suboptimal results. To this end, we first theoretically
analyze the effect of the constructed graph on FSC. Motivated by the analysis,
we propose a novel graph construction method with a node-adaptive graph filter
to learn graphs from noisy data. Then, all independent stages of conventional
FSC are integrated into a single objective function, forming an end-to-end
framework that inputs raw data and outputs discrete cluster labels. An
algorithm is developed to jointly and alternately update the variables in each
stage. Finally, we conduct extensive experiments on synthetic, benchmark, and
real data, which show that our model is superior to state-of-the-art fair
clustering methods.

我们提出了一种在组公平性约束下进行谱聚类的方法，通过从噪声数据中学习图构造方法和将传统的公平谱聚类的各个阶段整合到一个端到端的框架中，处理原始数据并输出离散的聚类标签。实验证明我们的模型优于现有的公平聚类方法。

一个统一的公平谱聚类框架及有效图学习

A Unified Framework for Fair Spectral Clustering With Effective Graph  Learning

The $k$-center problem is a classical clustering problem in which one is
asked to find a partitioning of a point set $P$ into $k$ clusters such that the
maximum radius of any cluster is minimized. It is well-studied. But what if we
add up the radii of the clusters instead of only considering the cluster with
maximum radius? This natural variant is called the $k$-min-sum-radii problem.
It has become the subject of more and more interest in recent years, inspiring
the development of approximation algorithms for the $k$-min-sum-radii problem
in its plain version as well as in constrained settings.
We study the problem for Euclidean spaces $\mathbb{R}^d$ of arbitrary
dimension but assume the number $k$ of clusters to be constant. In this case, a
PTAS for the problem is known (see Bandyapadhyay, Lochet and Saurabh, SoCG,
2023). Our aim is to extend the knowledge base for $k$-min-sum-radii to the
domain of fair clustering. We study several group fairness constraints, such as
the one introduced by Chierichetti et al. (NeurIPS, 2017). In this model, input
points have an additional attribute (e.g., colors such as red and blue), and
clusters have to preserve the ratio between different attribute values (e.g.,
have the same fraction of red and blue points as the ground set). Different
variants of this general idea have been studied in the literature. To the best
of our knowledge, no approximative results for the fair $k$-min-sum-radii
problem are known, despite the immense amount of work on the related fair
$k$-center problem.
We propose a PTAS for the fair $k$-min-sum-radii problem in Euclidean spaces
of arbitrary dimension for the case of constant $k$. To the best of our
knowledge, this is the first PTAS for the problem. It works for different
notions of group fairness.

在 Euclidean 空间中，我们提出了一个在常数 k 下为公平 $k$-min-sum-radii 问题提供 PTAS 的方法，这是该问题的首个 PTAS，适用于不同的群体公平性概念。

在高维空间中近似求解公平的 $k$ 最小总半径问题

Approximating Fair $k$-Min-Sum-Radii in $\mathbb{R}^d$

Submodular function optimization has numerous applications in machine
learning and data analysis, including data summarization which aims to identify
a concise and diverse set of data points from a large dataset. It is important
to implement fairness-aware algorithms when dealing with data items that may
contain sensitive attributes like race or gender, to prevent biases that could
lead to unequal representation of different groups. With this in mind, we
investigate the problem of maximizing a monotone submodular function while
meeting group fairness constraints. Unlike previous studies in this area, we
allow for randomized solutions, with the objective being to calculate a
distribution over feasible sets such that the expected number of items selected
from each group is subject to constraints in the form of upper and lower
thresholds, ensuring that the representation of each group remains balanced in
the long term. Here a set is considered feasible if its size does not exceed a
constant value of $b$. Our research includes the development of a series of
approximation algorithms for this problem.

通过开发近似算法解决具有组内公平性约束的单调子模函数最大化问题。