A Tutorial and Resources for Fair Clustering

Fair Clustering & Unsupervised Learning

The goal of this tutorial is to introduce a wide audience interested in algorithmic fairness to the nascent research area of fair clustering. Specifically, we wish to present a variety of fairness notions used in the context of clustering, argue about the necessity of each of those through corresponding applications, discuss the relationships between different notions, sketch the algorithmic ideas that were developed in order to address the corresponding computational problems, and finally share our thoughts about the future of research in algorithmic fairness. By the end of the tutorial, the audience will have achieved a significant level of familiarity with multiple definitions of fairness in the unsupervised learning context, and we hope that researchers will use these ideas in contexts both within and adjacent to the clustering context, in both industrial and academic applications.

Taxonomy of Fairness Concepts in Clustering (pdf) AAAI Tutorial Proposal (pdf)

Tutorial

AAAI 2022 Schedule — February 2022 — YouTube Playlist

Section	Speaker	Duration	Slides	Video
Introduction to Clustering Paradigms	Seyed Esmaeili	30 minutes + 5 minutes QnA	pdf, pptx	YouTube
Notions of Demographic Fairness	Marina Knittel and Leonidas Tsepenekas	1 hour + 5 minutes QnA	pdf, pptx	YouTube (#1), YouTube (#2)
Break		15 minutes
Notions of Individual Fairness	Leonidas Tsepenekas	45 minutes + 5 minutes QnA	pdf, pptx	YouTube
Algorithmic Aspects of Fair Clustering	Seyed Esmaeili	20 minutes + 5 minutes QnA	pdf, pptx	YouTube
Risks of Use and Advice for Responsible, Interdisciplinary Work	Brian Brubach	45 minutes + 5 minutes QnA	pdf, pptx	YouTube

Recommended Reading

If you see anything missing or have a suggestion, feel free to reach out!
Year	Title	Author	Topic	Link	Notes
Overview Papers
2012	Fairness Through Awareness	Cynthia Dwork, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Rich Zemel	Fair Machine Learning	arXiv:	Seminal paper on fairness in machine learning.
2021	An Overview of Fairness in Clustering	Anshuman Chhabra, Karina Masalkovaite, and Prasant Mohapatra	Survey	IEEE:	Survey paper
Group Fairness Papers
2017	Fair Clustering Through Fairlets	Flavio Chierichetti, Ravi Kumar, Silvio Lattanzi, and Sergei Vassilvitskii	Balance	arXiv:	Introduces demographic fairness and disparate impact to clustering.
2018	Privacy Preserving Clustering with Constraints	Clemens Rösner and Melanie Schmidt	Balance; Privacy	arXiv:	Combines privacy with balance and explores both separately.
2019	On the Cost of Essentially Fair Clusterings	Ioana O. Bercea, Martin Groß, Samir Khuller, Aounon Kumar, Clemens Rösner, Daniel R. Schmidt, and Melanie Schmidt	Balance; Essential Fairness	arXiv:	Introducess the notion of essential fairness, which sets the stage for bounded representation. Also explores fairness for many different problems.
2019	Guarantees for Spectral Clustering with Fairness Constraints	Matthäus Kleindessner, Samira Samadi, Pranjal Awasthi, Jamie Morgenstern	Balance; Spectral Clustering	arXiv:	To our knowledge, the only fair spectral clustering paper.
2019	Clustering without Over-Representation	Sara Ahmadian, Alessandro Epasto, Ravi Kumar, and Mohammad Mahdian	Bounded Representation	arXiv:	Formalized the general notion of alpha-capped representation.
2020	Fair Correlation Clustering	Sara Ahmadian, Alessandro Epasto, Ravi Kumar, Mohammad Mahdian	Bounded Representation; Correlation Clustering	arXiv:	Initiates the study of fair correlation clustering.
2020	Fair Hierarchical Clustering	Sara Ahmadian, Alessandro Epasto, Marina Knittel, Ravi Kumar, Mohammad Mahdian, Benjamin Moseley, Philip Pham, Sergei Vassilvitskii, and Yuyan Wang	Bounded Representation; Hierarchical Clustering	arXiv:	Initiates the study of fair hierarchical clustering.
2019	Fair Algorithms for Clustering	Suman K. Bera, Deeparnab Chakrabarty, Nicolas J. Flores, and Maryam Negahbani	Bounded Representation	arXiv:	Formalizes the general notion of bounded representation.
2020	Probabilistic Fair Clustering	Seyed A. Esmaeili, Brian Brubach, Leonidas Tsepenekas, and John P. Dickerson	Bounded Representation; Probabilistic Fairness	arXiv:	Introduces fairness under a probabilistic model (color assignment is random).
2021	Fair Clustering Under a Bounded Cost	Seyed A. Esmaeili, Brian Brubach, Aravind Srinivasan, and John P. Dickerson	Bounded Representation; Bounded Cost	arXiv:	Formalizes fairness as an optimization problem under bounded cost constraints.
2019	Fair k-Center Clustering for Data Summarization	Matthäus Kleindessner, Pranjal Awasthi, and Jamie Morgenstern	Cluster Center Fairness	arXiv:	Initiates the study of fairness for data summarization tasks.
2020	Fair k-centers via Maximum Matching	Matthew Jones, Huy Le Nguyen, and Thy Nguyen	Cluster Center Fairness	link:	Extends results for fair data summarization.
2021	Diversity-aware k-median: Clustering with fair center representation	Suhas Thejaswi, Bruno Ordozgoiti, and Aristides Gionis	Cluster Center Fairness	arXiv:	Further extends results for fair data summarization.
2019	Proportionally Fair Clustering	Xingyu Chen, Brandon Fain, Liang Lyu, and Kamesh Munagala	Proportional Fairness	arXiv:	Introduces proportional fairness.
2020	Proportionally Fair Clustering Revisited	Evi Micha and Nisarg Shah	Proportional Fairness	link:	Extends results for proportional fairness.
2019	A Constant Approximation for Colorful k-Center	Sayan Bandyapadhyay, Tanmay Inamdar, Shreyas Pai, and Kasturi Varadarajan	Fairness with Outliers	arXiv:	Introduces fairness with outliers.
2020	Fair Colorful k-Center Clustering	Xinrui Jia, Kshiteej Sheth, and Ola Svensson	Fairness with Outliers	arXiv:	Extends results for fairness with outliers.
2020	A Technique for Obtaining True Approximations for k-Center with Covering Constraints	Georg Anegg, Haris Angelidakis, Adam Kurpisz, and Rico Zenklusen	Fairness with Outliers	arXiv:	Further extends results for fairness with outliers.
2021	Fair Clustering via Equitable Group Representations	Mohsen Abbasi, Aditya Bhaskara, and Suresh Venkatasubramanian	Socially Fair Clustering	arXiv:	Introduces socially fair clustering.
2021	Socially Fair 𝑘-Means Clustering	Mehrdad Ghadiri, Samira Samadi, and Santosh Vempala	Socially Fair Clustering	arXiv:	Concurrently introduced socially fair clustering.
2021	Approximation Algorithms for Socially Fair Clustering	Yury Makarychev and Ali Vakilian	Socially Fair Clustering	arXiv:	Extends results for socially fair clustering.
2021	Tight FPT Approximation for Socially Fair Clustering	Dishant Goyal and Ragesh Jaiswal	Socially Fair Clustering	arXiv:	Further extends results for socially fair clustering.
Individual Fairness Papers
2021	Fairness, Semi-Supervised Learning, and More: A General Framework for Clustering with Stochastic Pairwise Constraints	Brian Brubach, Darshan Chakrabarti, John P. Dickerson, Aravind Srinivasan, Leonidas Tsepenekas	Dwork et al. Paradigm	arXiv:
2020	Distributional Individual Fairness for Clustering	Nihesh Anderson, Suman K. Bera, Syamantak Das, and Yang Liu	Dwork et al. Paradigm	arXiv:
2021	Feature-based Individual Fairness in k-Clustering	Debajyoti Kar, Sourav Medya, Debmalya Mandal, Arlei Silva, Palash Dey, and Swagato Sanyal	Dwork et al. Paradigm	arXiv:
2021	A New Notion of Individually Fair Clustering: α-Equitable k-Center	Darshan Chakrabarti, John P. Dickerson, Seyed A. Esmaeili, Aravind Srinivasan, and Leonidas Tsepenekas	Dwork et al. Paradigm	arXiv:
2019	A Center in Your Neighborhood: Fairness in Facility Location	Christopher Jung, Sampath Kannan, and Neil Lutz	Center in my Neighborhood	arXiv:
2020	Individual Fairness for k-Clustering	Sepideh Mahabadi and Ali Vakilian	Center in my Neighborhood	arXiv:
2021	Better Algorithms for Individually Fair k-Clustering	Deeparnab Chakrabarty and Maryam Negahbani	Center in my Neighborhood	arXiv:
2021	Improved Approximation Algorithms for Individually Fair Clustering	Ali Vakilian and Mustafa Yalçıner	Center in my Neighborhood	arXiv:
2017	A Lottery Model for Center-type Problems With Outliers	David G. Harris, Thomas Pensyl, Aravind Srinivasan, and Khoa Trinh	Fairness with Outliers	arXiv:
2020	A Technique for Obtaining True Approximations for k-Center with Covering Constraints	Georg Anegg, Haris Angelidakis, Adam Kurpisz, and Rico Zenklusen	Fairness with Outliers	arXiv:
2020	A Notion of Individual Fairness for Clustering	Matthäus Kleindessner, Pranjal Awasthi, and Jamie Morgenstern	Center Locality	arXiv:

About Us

This is ongoing research and work led by the following team; if you are interested in joining, please feel free to reach out!

Pranjal Awasthi (Google): Pranjal Awasthi is a research scientist at Google. His research interests include the design of robust algorithms for supervised and unsupervised learning, theory of ML fairness, and active learning.
Brian Brubach (Wellesley): Brian Brubach is an Assistant Professor of Computer Science at Wellesley College and an Affiliate of the Institute for Mathematics and Democracy. His research focuses on algorithms and theoretical computer science with broad applications in areas such as e-commerce, algorithmic fairness, and electoral systems.
Deeparnab Chakrabarty (Dartmouth): Deeparnab Chakrabarty is an associate professor of computer science at Dartmouth. His research interests involve the interplay of optimization and algorithms, with applications in data science, machine learning, and algorithmic economics.
John Dickerson (UMD & Arthur): John P Dickerson is Assistant Professor of Computer Science at Maryland, as well as Chief Scientist of Arthur AI. He is recipient of the NSF CAREER Award, IEEE Intelligent Systems AI's 10 to Watch, and a Google Faculty Research Award, and others. His research centers on solving economic problems using techniques from stochastic optimization and machine learning.
Seyed Esmaeili (UMD): Seyed Esmaeili is a 5th year PhD student at the University of Maryland, College Park. His research interests are in machine learning, algorithms, and fairness. More specifically, his work focuses on producing algorithms with theoretical guarantees that address fairness issues in various topics such as clustering, matching, and redistricting.
Matthäus Kleindessner (Amazon): Matthäus Kleindessner is a Research Scientist at Amazon AWS in Tübingen, Germany, working on algorithmic fairness. He has a PhD from the University of Tübingen and did postdocs at Rutgers University and the University of Washington.
Marina Knittel (UMD): Marina Knittel is a fourth year PhD student at the University of Maryland studying theoretical computer science and artificial intelligence. Her research focuses on fairness and scalability for algorithms on massive networks, including adaptive and non-adaptive massively parallel computation (AMPC and MPC), fairness in graph partitioning, and mechanism design.
Jamie Morgenstern (UW & Google): Jamie Morgenstern is an assistant professor at the University of Washington. She studies the social impact of machine learning and the impact of social behavior on ML's guarantees. How should machine learning be made robust to behavior of the people generating training or test data for it? How should we ensure that the models we design do not exacerbate inequalities already present in society?
Samira Samadi (MPI-IS): Samira Samadi is a research group leader at the Max Planck Institute for Intelligent Systems in Tübingen, Germany. She studies the interactions between humans and ML and uses her findings to design ML systems that augment humans’ abilities. She got her Ph.D. from the School of Computer Science at Georgia Tech.
Aravind Srinivasan (UMD & Amazon): Aravind Srinivasan is a Distinguished University Professor and Professor of Computer Science at the University of Maryland, College Park. His research interests include algorithms, probabilistic methods, data science, network science, and machine learning: theory, and applications in areas including health, E-commerce, cloud computing, Internet advertising, and fairness.
Leo Tsepenekas (UMD): Leonidas Tsepenekas is a 5th year PhD student at the University of Maryland, College Park. Leonidas' research interests revolve around Algorithmic Fairness and Stochastic Models for Combinatorial Optimization. Specifically, he is interested in identifying meaningful notions of fairness, translating them into rigorous mathematical objects, and incorporating them in classical algorithmic problems.