Spectral Normalized-Cut Graph Partitioning with Fairness Constraints

Tutkimustuotos: Artikkeli kirjassa/raportissa/konferenssijulkaisussaKonferenssiartikkeliTieteellinenvertaisarvioitu

Abstrakti

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.

Alkuperäiskielienglanti
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
Sivumäärä9
KustantajaIOS Press BV
Julkaisupäivä28 syysk. 2023
Sivut1389-1397
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

Julkaisusarja

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

Lisätietoja

Publisher Copyright:
© 2023 The Authors.

Tieteenalat

  • 113 Tietojenkäsittely- ja informaatiotieteet

Siteeraa tätä