Guarantees for Spectral Clustering with Fairness Constraints

Matthäus Kleindessner, Samira Samadi, Pranjal Awasthi, Jamie Morgenstern
Proceedings of the 36th International Conference on Machine Learning, PMLR 97:3458-3467, 2019.

Abstract

Given the widespread popularity of spectral clustering (SC) for partitioning graph data, we study a version of constrained SC in which we try to incorporate the fairness notion proposed by Chierichetti et al. (2017). According to this notion, a clustering is fair if every demographic group is approximately proportionally represented in each cluster. To this end, we develop variants of both normalized and unnormalized constrained SC and show that they help find fairer clusterings on both synthetic and real data. We also provide a rigorous theoretical analysis of our algorithms on a natural variant of the stochastic block model, where $h$ groups have strong inter-group connectivity, but also exhibit a “natural” clustering structure which is fair. We prove that our algorithms can recover this fair clustering with high probability.

Cite this Paper

BibTeX
@InProceedings{pmlr-v97-kleindessner19b, title = {Guarantees for Spectral Clustering with Fairness Constraints}, author = {Kleindessner, Matth{\"a}us and Samadi, Samira and Awasthi, Pranjal and Morgenstern, Jamie}, booktitle = {Proceedings of the 36th International Conference on Machine Learning}, pages = {3458--3467}, year = {2019}, editor = {Chaudhuri, Kamalika and Salakhutdinov, Ruslan}, volume = {97}, series = {Proceedings of Machine Learning Research}, month = {09--15 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v97/kleindessner19b/kleindessner19b.pdf}, url = {https://proceedings.mlr.press/v97/kleindessner19b.html}, abstract = {Given the widespread popularity of spectral clustering (SC) for partitioning graph data, we study a version of constrained SC in which we try to incorporate the fairness notion proposed by Chierichetti et al. (2017). According to this notion, a clustering is fair if every demographic group is approximately proportionally represented in each cluster. To this end, we develop variants of both normalized and unnormalized constrained SC and show that they help find fairer clusterings on both synthetic and real data. We also provide a rigorous theoretical analysis of our algorithms on a natural variant of the stochastic block model, where $h$ groups have strong inter-group connectivity, but also exhibit a “natural” clustering structure which is fair. We prove that our algorithms can recover this fair clustering with high probability.} }
Endnote
%0 Conference Paper %T Guarantees for Spectral Clustering with Fairness Constraints %A Matthäus Kleindessner %A Samira Samadi %A Pranjal Awasthi %A Jamie Morgenstern %B Proceedings of the 36th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2019 %E Kamalika Chaudhuri %E Ruslan Salakhutdinov %F pmlr-v97-kleindessner19b %I PMLR %P 3458--3467 %U https://proceedings.mlr.press/v97/kleindessner19b.html %V 97 %X Given the widespread popularity of spectral clustering (SC) for partitioning graph data, we study a version of constrained SC in which we try to incorporate the fairness notion proposed by Chierichetti et al. (2017). According to this notion, a clustering is fair if every demographic group is approximately proportionally represented in each cluster. To this end, we develop variants of both normalized and unnormalized constrained SC and show that they help find fairer clusterings on both synthetic and real data. We also provide a rigorous theoretical analysis of our algorithms on a natural variant of the stochastic block model, where $h$ groups have strong inter-group connectivity, but also exhibit a “natural” clustering structure which is fair. We prove that our algorithms can recover this fair clustering with high probability.
APA
Kleindessner, M., Samadi, S., Awasthi, P. & Morgenstern, J.. (2019). Guarantees for Spectral Clustering with Fairness Constraints. Proceedings of the 36th International Conference on Machine Learning, in Proceedings of Machine Learning Research 97:3458-3467 Available from https://proceedings.mlr.press/v97/kleindessner19b.html.

Related Material