Spectral Normalized-Cut Graph Partitioning with Fairness Constraints
Not on the map. Why?
Abstract (arXiv)
Normalized-cut graph partitioning aims to divide the set of nodes in a graph into k disjoint clusters to minimize the fraction of the total edges between any cluster and all other clusters. In this paper, we consider a fair variant of the partitioning problem wherein nodes are characterized by a categorical sensitive attribute (e.g., gender or race) indicating membership to different demographic groups. Our goal is to ensure that each group is approximately proportionally represented in each cluster while minimizing the normalized cut value. To resolve this problem, we propose a two-phase spectral algorithm called FNM. In the first phase, we add an augmented Lagrangian term based on our fairness criteria to the objective function for obtaining a fairer spectral node embedding. Then, in the second phase, we design a rounding scheme to produce k clusters from the fair embedding that effectively trades off fairness and partition quality. Through comprehensive experiments on nine benchmark datasets, we demonstrate the superior performance of FNM compared with three baseline methods.
Key facts. Cited by 3 papers in the map (data through 7 Oct 2026). Builds on 31 of its 70 references that are in the map. First posted on arXiv 22 Jul 2023.
Builds on
31 of 70 references.
References · 31
- 2016node2vec: Scalable Feature Learning for Networkscited by 1,913
- 2019A Survey on Bias and Fairness in Machine Learningcited by 1,911
- 2014DeepWalk: Online Learning of Social Representationscited by 1,543
- 2017Fairness in Criminal Justice Risk Assessments: The State of the Artcited by 315
- 2018A comparative study of fairness-enhancing interventions in machine learningcited by 208
- 2018Fair Clustering Through Fairletscited by 176
- 2020Ethical Machine Learning in Health Carecited by 112
- 2019Fair Algorithms for Clusteringcited by 98
- 2019Scalable Fair Clusteringcited by 78
- 2022Fairness in Graph Mining: A Surveycited by 76
- 2019Guarantees for Spectral Clustering with Fairness Constraintscited by 72
- 2019Proportionally Fair Clusteringcited by 69
19 more
- 2019Fair k-Center Clustering for Data Summarizationcited by 65
- 2015Contact patterns in a high school: a comparison between data collected using wearable sensors, contact diaries and friendship surveyscited by 59
- 2020Individual Fairness for k-Clusteringcited by 56
- 2019Coresets for Clustering with Fairness Constraintscited by 51
- 2018On the cost of essentially fair clusteringscited by 44
- 2021Improved Approximation Algorithms for Individually Fair Clusteringcited by 33
- 2019Multimodal Style Transfer via Graph Cutscited by 32
- 2020Probabilistic Fair Clusteringcited by 28
- 2021Better Algorithms for Individually Fair k-Clusteringcited by 28
- 2020Fair Correlation Clusteringcited by 27
- 2021Approximation Algorithms for Socially Fair Clusteringcited by 25
- 2021Fair Clustering Under a Bounded Costcited by 21
- 2021Diversity-aware k-median : Clustering with fair center representationcited by 16
- 2022Scalable Spectral Clustering with Group Fairness Constraintscited by 16
- 2021Approximating Fair Clustering with Cascaded Norm Objectivescited by 13
- 2021Consistency of Constrained Spectral Clustering under Graph Induced Fair Planted Partitionscited by 10
- 2022Improved Approximation for Fair Correlation Clusteringcited by 6
- 2019Affirmative Action Policies for Top-k Candidates Selection, With an Application to the Design of Policies for University Admissionscited by 5
- 2021Efficient Algorithms For Fair Clustering with a New Fairness Notioncited by 5
Built on by
Citing papers per year: 2023: 1; 2024: 0; 2025: 1; 2026: 1.
3 papers.