Spectral Normalized-Cut Graph Partitioning with Fairness Constraints

Abstract

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.

arXiv comment17 pages, 7 figures, accepted to the 26th European Conference on Artificial Intelligence (ECAI 2023)

References in corpus (15)

• DeepWalk: Online Learning of Social Representations
• Finding community structure in networks using the eigenvectors of matrices
• Contact patterns in a high school: a comparison between data collected using wearable sensors, contact diaries and friendship surveys
• node2vec: Scalable Feature Learning for Networks
• Guarantees for Spectral Clustering with Fairness Constraints
• Fair k-Center Clustering for Data Summarization
• Individual Fairness for $k$-Clustering
• Efficient Algorithms For Fair Clustering with a New Fairness Notion
• Approximation Algorithms for Socially Fair Clustering
• Better Algorithms for Individually Fair $k$-Clustering
• Scalable Spectral Clustering with Group Fairness Constraints
• Improved Approximation Algorithms for Individually Fair Clustering
• Consistency of Constrained Spectral Clustering under Graph Induced Fair Planted Partitions
• Improved Approximation for Fair Correlation Clustering
• Affirmative Action Policies for Top-k Candidates Selection, With an Application to the Design of Policies for University Admissions

Cited by in corpus (1)

• A Deep Latent Factor Graph Clustering with Fairness-Utility Trade-off Perspective