A Generic Framework for Fair Consensus Clustering in Streams

Consensus clustering seeks to combine multiple clusterings of the same dataset, potentially derived by considering various non-sensitive attributes by different agents in a multi-agent environment, intoasinglepartitioningthatbestreflectstheoverall structure of the underlying dataset. Recent work by Chakraborty et al. [COLT’25] introduced a fair variant under proportionate fairness and obtained a constant-factor approximation by naively selecting the best closest fair input clustering; however, their offline approach requires storing all input clusterings, which is prohibitivelyexpensive for most large-scale applications. In this paper, we initiate the study of fair consensus clustering in the streaming model, where input clusterings arrive sequentially andmemoryislimited. Wedesignthefirstconstant-factoralgorithm thatprocessesthestreamwhilestoringonlyalogarithmicnumberof inputs. Enroute, weintroduceanewgenericalgorithmicframework that integrates closest fair clustering with cluster fitting, yielding improved approximation guarantees not only in the streaming settingbutalsowhenrevisitedoffline. Furthermore, theframework is fairness-agnostic: it applies to any fairness definition for which anapproximatelyclosefairclusteringcanbecomputedefficiently. Finally, we extend our methods to the more general 𝑘-median consensusclustering problem.

Authors

• Diptarka Chakraborty National University of Singapore
• Kushagra Chatterjee National University of Singapore
• Debarati Das Pennsylvania State University
• Tien-Long Nguyen Pennsylvania State University

Keywords

• Consensus Clustering
• Fairness
• Approximation Algorithms