Oral
Guarantees for Spectral Clustering with Fairness Constraints
Matthäus Kleindessner · Samira Samadi · Pranjal Awasthi · Jamie Morgenstern

Thu Jun 13th 12:10 -- 12:15 PM @ Room 103

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. While there have been efforts to incorporate various constraints into the SC framework, theoretically analyzing them is a challenging problem. We overcome this by proposing 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.

Author Information

Matthäus Kleindessner (Rutgers University)
Samira Samadi (Georgia Tech)
Pranjal Awasthi (Rutgers University)
Jamie Morgenstern (Georgia Institute of Technology)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors