A Unified Framework for Fair Spectral Clustering With Effective Graph
  Learning
Xiang Zhang Qiao Wang
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.