Spectral Normalized-Cut Graph Partitioning with Fairness Constraints

Tutkimustuotos: Artikkeli kirjassa/raportissa/konferenssijulkaisussaKonferenssiartikkeliTieteellinenvertaisarvioitu


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.

OtsikkoECAI 2023 - 26th European Conference on Artificial Intelligence, including 12th Conference on Prestigious Applications of Intelligent Systems, PAIS 2023 - Proceedings
ToimittajatKobi Gal, Kobi Gal, Ann Nowe, Grzegorz J. Nalepa, Roy Fairstein, Roxana Radulescu
KustantajaIOS Press BV
Julkaisupäivä28 syysk. 2023
ISBN (elektroninen)9781643684369
DOI - pysyväislinkit
TilaJulkaistu - 28 syysk. 2023
OKM-julkaisutyyppiA4 Artikkeli konferenssijulkaisuussa
TapahtumaEuropean Conference on Artificial Intelligence - Krakow, Puola
Kesto: 30 syysk. 20234 lokak. 2023
Konferenssinumero: 26


NimiFrontiers in Artificial Intelligence and Applications
ISSN (painettu)0922-6389


Publisher Copyright:
© 2023 The Authors.


  • 113 Tietojenkäsittely- ja informaatiotieteet

Siteeraa tätä