Individual Fairness in Graph Decomposition

Kamesh Munagala, Govind S. Sankar
Proceedings of the 41st International Conference on Machine Learning, PMLR 235:36723-36742, 2024.

Abstract

In this paper, we consider classic randomized low diameter decomposition procedures for planar graphs that obtain connected clusters that are cohesive in that close by pairs of nodes are assigned to the same cluster with high probability. We consider the additional aspect of individual fairness – pairs of nodes at comparable distances should be separated with comparable probability. We show that classic decomposition procedures do not satisfy this property. We present novel algorithms that achieve various trade-offs between this property and additional desiderata of connectivity of the clusters and optimality in number of clusters. We show that our individual fairness bounds may be difficult to improve by tying the improvement to resolving a major open question in metric embeddings. We finally show the efficacy of our algorithms on real planar networks modeling Congressional redistricting.

Cite this Paper

BibTeX
@InProceedings{pmlr-v235-munagala24a, title = {Individual Fairness in Graph Decomposition}, author = {Munagala, Kamesh and S. Sankar, Govind}, booktitle = {Proceedings of the 41st International Conference on Machine Learning}, pages = {36723--36742}, year = {2024}, editor = {Salakhutdinov, Ruslan and Kolter, Zico and Heller, Katherine and Weller, Adrian and Oliver, Nuria and Scarlett, Jonathan and Berkenkamp, Felix}, volume = {235}, series = {Proceedings of Machine Learning Research}, month = {21--27 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v235/main/assets/munagala24a/munagala24a.pdf}, url = {https://proceedings.mlr.press/v235/munagala24a.html}, abstract = {In this paper, we consider classic randomized low diameter decomposition procedures for planar graphs that obtain connected clusters that are cohesive in that close by pairs of nodes are assigned to the same cluster with high probability. We consider the additional aspect of individual fairness – pairs of nodes at comparable distances should be separated with comparable probability. We show that classic decomposition procedures do not satisfy this property. We present novel algorithms that achieve various trade-offs between this property and additional desiderata of connectivity of the clusters and optimality in number of clusters. We show that our individual fairness bounds may be difficult to improve by tying the improvement to resolving a major open question in metric embeddings. We finally show the efficacy of our algorithms on real planar networks modeling Congressional redistricting.} }
Endnote
%0 Conference Paper %T Individual Fairness in Graph Decomposition %A Kamesh Munagala %A Govind S. Sankar %B Proceedings of the 41st International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2024 %E Ruslan Salakhutdinov %E Zico Kolter %E Katherine Heller %E Adrian Weller %E Nuria Oliver %E Jonathan Scarlett %E Felix Berkenkamp %F pmlr-v235-munagala24a %I PMLR %P 36723--36742 %U https://proceedings.mlr.press/v235/munagala24a.html %V 235 %X In this paper, we consider classic randomized low diameter decomposition procedures for planar graphs that obtain connected clusters that are cohesive in that close by pairs of nodes are assigned to the same cluster with high probability. We consider the additional aspect of individual fairness – pairs of nodes at comparable distances should be separated with comparable probability. We show that classic decomposition procedures do not satisfy this property. We present novel algorithms that achieve various trade-offs between this property and additional desiderata of connectivity of the clusters and optimality in number of clusters. We show that our individual fairness bounds may be difficult to improve by tying the improvement to resolving a major open question in metric embeddings. We finally show the efficacy of our algorithms on real planar networks modeling Congressional redistricting.
APA
Munagala, K. & S. Sankar, G.. (2024). Individual Fairness in Graph Decomposition. Proceedings of the 41st International Conference on Machine Learning, in Proceedings of Machine Learning Research 235:36723-36742 Available from https://proceedings.mlr.press/v235/munagala24a.html.

Related Material