acceptodds
Under review as a conference paper at ICLR 2027

Allocation-Dependent Distortion for Fair Clustering Ensembles

Abstract

Clustering ensembles combine multiple base partitions into a final consensus. When protected groups are present, the consensus must also account for how each group is distributed across the output clusters relative to the marginal cluster masses. We study allocation-dependent distortion, in which the conditional proportion of a group assigned to a cluster directly weights the distortion of that same group–cluster cell. The resulting Fair -means Consensus Clustering (FKCC) objective incorporates group representation into consensus aggregation without enforcing profile alignment as a hard constraint. We show that the complete objective can move profile discrepancy in either direction. Fixed-distortion analysis characterizes the allocation response and identifies when quadratic group profiles coincide or remain close; it also explains the special role of the quadratic coefficient within the positive-power family. Center elimination yields an exact finite objective with monotone one-object descent. An algebraic finite–empirical identity holds for feasible induced assignments, while uniform estimation is established separately under a fixed-representation sampling model. Experiments on nine datasets show strong clustering utility and consistent matched reductions in profile discrepancy on the tested benchmarks. Anonymous code is available at https://anonymous.4open.science/r/method_code-F99B.

Primary area:
unsupervised, self-supervised, semi-supervised, and supervised representation learning
Keywords:
Clustering ensembles

Reviews

Among:
Shape:
1234this paper, Top 1%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.67 over 3 reviews, above 99% of the others.
Reviewer_ZCL6OpenReview ↗
Rating
4
Confidence
3
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The authors present a clustering method called Fair K-means Consensus Clustering, a method that incorporates group fairness in ensemble clustering. Existing approaches involve fairness constraints or add a regularization, but this paper proposes a method that adds an allocation dependent weighing mechanism directly into the clustering objective. The authors do so by adjusting how much each group's clustering error contributes to the objective based on the proportion of that group assigned to each cluster. This encourages a more balanced distribution of protected groups across clusters while still considering how well the data points fit their assigned clusters.

The main contribution of the paper is the new allocation-dependent clustering objective that adds group fairness directly into the clustering process by adding a weightage term to the clustering error based on how protected groups are distributed across clusters. The second contribution is the theoretical analysis of this objective, examination of when it can increase or worsen fairness and under what conditions different groups can achieve similar distributions. Last, they derive an efficient optimization algorithm that iteratively improves cluster assignments and guarantees convergence to a local optimum.

For validation, the evaluate their approach on nine datasets of different sizes and domains, comparing it against several existing ensemble clustering and fair clustering methods. They evaluate both clustering quality, using metrics such as ACC, NMI, and ARI, and group fairness using representation-based metrics. The results show that the proposed method generally improves both clustering performance and group representation, particularly compared to standard K-means Consenus Clustering.

Critical strengths

(S1) The formulation of the clustering algorithm that directly incorporates the weighing of protected groups into the algorithm without leaning on additional regularisation terms is quite novel and promising work. This is an interesting methodological contribution, as it provides an alternative way to address fairness while maintaining clustering quality.

(S2) There is a strong theoretical analysis of the proposed objective, including the behaviour of group allocations, the justification of the quadratic weighing and the convergence property of the optimization algorithm.

(S3) The authors also acknowledge and theoretically demonstrate cases where their method may not improve fairness, rather than claiming that fairness is always guaranteed. This makes the theoretical contribution more convincing.

(S4) The authors evaluate the method on nine datasets of differing size and domains, and the method is compared against a large number of existing fair clustering and ensemble clustering methods. The experiments show improvements in both clustering quality and fairness, particularly in the matched comparison with standard KCC, which is the direct algorithm from which this is derived.

Critical weaknesses

(W1) One of the main concerns is that the uniform-convergence analysis the authors use assumes a fixed representation that is independent of the samples used for clustering. However, in the experiments, the ensemble representations are constructed using the same dataset on which clustering is performed. But the authors acknowledge this distinction, but it means that the statistical guarantees do not directly apply to their actual experimental pipeline. A theoretical extension covering the data-dependent ensemble construction, or additional experiments investigating generalization to unseen samples, would strengthen the paper.

Questions for authors

none

1 comment
AuthorsOpenReview ↗

Fixed-representation assumption and independent-reference evaluation

We thank the reviewer for the comments and suggestions. The uniform-estimation result in Section 4.2 concerns the FKCC aggregation objective under a representation rule fixed independently of the aggregation sample. The manuscript distinguishes this sampling model from the same-sample construction used in the main experiments. Following your suggestion for additional experiments, we conducted an independent-reference experiment while retaining the original FKCC objective and solver.

For each dataset, we randomly divided objects within each protected group into approximately equal reference and aggregation sets. The reference set alone was used to estimate preprocessing statistics where needed, generate 20 base partitions with their corresponding cluster centers, and determine the ensemble-representation rule. The base-partition cluster counts were sampled from [k,⌈n⌉][k,\lceil\sqrt n\rceil], with nn the full dataset size and kk the target consensus cluster count. The reference centers and representation rule were then fixed. Each aggregation object was assigned to the nearest cluster center for each reference partition, and its representation was constructed using the fixed rule. KCC and FKCC were optimized separately from identical initial assignments on the same aggregation representations. We evaluated their final partitions only on the aggregation objects, using ten random splits per dataset.

The table reports mean ± population standard deviation over the ten splits.

DatasetMethodACCNMIARIMNCEFfairF_{\mathrm{fair}}
CKDKCC0.9265 ± 0.01270.6742 ± 0.03540.7267 ± 0.04320.9069 ± 0.03200.9162 ± 0.0163
CKDFKCC0.9295 ± 0.01270.6828 ± 0.04110.7371 ± 0.04430.9241 ± 0.02660.9265 ± 0.0140
COIL20KCC0.6764 ± 0.03260.7847 ± 0.01810.6205 ± 0.03120.8586 ± 0.03940.7556 ± 0.0210
COIL20FKCC0.7267 ± 0.02540.8064 ± 0.01240.6668 ± 0.01730.9203 ± 0.02560.8116 ± 0.0160
MFEATKCC0.7911 ± 0.08040.7830 ± 0.03060.7027 ± 0.06070.9730 ± 0.01380.8705 ± 0.0518
MFEATFKCC0.8763 ± 0.05460.8182 ± 0.03060.7783 ± 0.05530.9853 ± 0.00760.9266 ± 0.0322
BillionairesKCC0.7582 ± 0.11390.3273 ± 0.19630.3179 ± 0.22220.9553 ± 0.04210.8407 ± 0.0789
BillionairesFKCC0.8671 ± 0.08810.5088 ± 0.24240.5697 ± 0.23680.9894 ± 0.01020.9221 ± 0.0553
USPS3568KCC0.7551 ± 0.10270.6269 ± 0.05880.6019 ± 0.09160.9944 ± 0.00450.8547 ± 0.0678
USPS3568FKCC0.8862 ± 0.03960.7080 ± 0.04490.7403 ± 0.06040.9979 ± 0.00160.9382 ± 0.0234
HARKCC0.6367 ± 0.06580.6584 ± 0.03520.5392 ± 0.06450.8797 ± 0.10030.7338 ± 0.0574
HARFKCC0.6990 ± 0.08670.6385 ± 0.06610.5487 ± 0.08500.9809 ± 0.01100.8136 ± 0.0642
CensusKCC0.5933 ± 0.08960.0486 ± 0.05060.0623 ± 0.07600.9967 ± 0.00230.7398 ± 0.0698
CensusFKCC0.7006 ± 0.00390.1240 ± 0.00480.1609 ± 0.00630.9991 ± 0.00020.8236 ± 0.0027
OULADKCC0.6411 ± 0.08210.0829 ± 0.08110.1062 ± 0.10050.9619 ± 0.02220.7653 ± 0.0521
OULADFKCC0.7209 ± 0.04120.1509 ± 0.04580.2020 ± 0.06030.9810 ± 0.00520.8303 ± 0.0275
FairFaceKCC0.8254 ± 0.09580.3963 ± 0.13150.4602 ± 0.15190.9515 ± 0.11940.8840 ± 0.1065
FairFaceFKCC0.8572 ± 0.00210.4131 ± 0.00540.5103 ± 0.00590.9953 ± 0.00040.9211 ± 0.0012

FKCC achieves higher mean ACC, ARI, MNCE, and FfairF_{\mathrm{fair}} on all nine datasets, and higher mean NMI on eight (the exception is HAR). Averaging the dataset-level means equally, the improvements over KCC are 0.0733 in ACC, 0.0520 in NMI, 0.0863 in ARI, 0.0328 in MNCE, and 0.0614 in FfairF_{\mathrm{fair}}.

Across the 90 paired runs, FKCC improves ACC in 72 runs (4 ties), and improves MNCE and FfairF_{\mathrm{fair}} in 83 runs each (2 ties each).

We also measured group-allocation profile discrepancy Δprof\Delta_{\mathrm{prof}} and average total variation (AvgTV), which compare each group's allocation distribution with the marginal cluster distribution. Both have lower dataset-level means on all nine datasets. Their equal-dataset averages decrease from 0.0148 to 0.0066 and from 0.0630 to 0.0409, respectively.

The new aggregation objects participate in consensus optimization but are excluded from constructing the reference partitions and fitting the representation rule. These results provide additional empirical evidence that FKCC's gains in clustering quality and group representation persist under this independent-reference protocol.

Reviewer_2XtJOpenReview ↗
Rating
4
Confidence
3
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

This paper studies group-representation fairness in clustering ensembles and proposes FKCC, which incorporates protected-group allocation into consensus distortion through assignment-dependent weights. The method is optimized using a center-eliminated objective and is supported by theoretical results on allocation behavior and statistical properties.

The experiments cover nine datasets with both observed and synthetic group labels. Comparisons with clustering ensemble and fairness-aware baselines assess clustering quality and group representation. In particular, the matched KCC–FKCC experiments show improvements in both aspects under the same base partitions and representation. Additional robustness and sensitivity studies support the empirical findings.

Critical strengths
  1. The paper considers group-representation fairness in terms of statistical independence between protected-group membership and consensus cluster assignments. It adopts a soft fairness mechanism that considers group allocation and consensus quality together without enforcing exact representation constraints. The matched KCC–FKCC comparisons, using the same base partitions and representation, show improved MNCE and clustering accuracy on average, along with reduced group-profile discrepancy. The joint fairness–utility results further support the effectiveness of this approach.
  2. The paper derives the optimal allocation profile under fixed positive cell-average distortions and characterizes the special role of quadratic weighting within the positive-power family. It also establishes an exact finite–empirical identity for feasible induced assignments and a stability bound for the center-eliminated risk. The numerical results are consistent with the closed-form allocation and stability analyses.
Critical weaknesses

The experiments cover datasets with different protected-group structures, but do not separately examine the effect of substantial group-size imbalance. A controlled analysis would help clarify whether the improvements in clustering quality and group representation, including worst-group allocation deviation, persist under such conditions. It would also be useful to examine the impact on convergence behavior and runtime.

Questions for authors
  1. The matched KCC–FKCC experiments report average improvements and the number of favorable runs. Could the authors additionally provide confidence intervals or paired statistical tests to assess the reliability of the improvements in clustering accuracy and group-representation fairness?
  2. The synthetic protected groups are generated with equal probabilities within each ground-truth class. How does the fairness–utility performance of FKCC change when protected-group membership becomes more strongly associated with the underlying class structure?
2 comments
AuthorsOpenReview ↗

Group-size imbalance and runtime (1/2)

Thank you for suggesting a statistical assessment of the paired improvements. In preparing this analysis, we rechecked the matched KCC–FKCC results and corrected the KCC reference results in the corresponding tables and figures (Tables 9–10 and Figures 1 and 3), together with the related experimental descriptions. KCC and FKCC use the same representation and initial partition and are optimized independently. The FKCC results are unchanged, and the main conclusions remain supported.

W1. Group-size imbalance and runtime

We conducted a controlled experiment on all nine datasets with target maximum-to-minimum group-size ratios R∈1,2,4,8,10R\in\\{1,2,4,8,10\\}. We kept the total sample size fixed within each dataset. At R=1R=1, the groups have equal size. For larger ratios, we reduced the sampling quota of one prespecified group and divided the remaining quota as evenly as possible among the other groups, rounding counts to integers while preserving the total. We sampled without replacement within the original group-class strata and kept the group labels unchanged. Ten repetitions per setting gave 450 paired KCC-FKCC comparisons, each using the same input and initial labels.

We report the paper's MNCE, Δprof\Delta_{\mathrm{prof}}, and AvgTV, and assess worst-group representation using maximum proportional violation. Following Esmaeili et al. (2021), we set both target bounds to each group's share in the subsample:

Vmax⁡=max⁡tmax⁡q:nq>0∣ntqnq−ntn∣.V_{\max}=\max_t\max_{q:n_q>0}\left|\frac{n_{tq}}{n_q}-\frac{n_t}{n}\right|.

Here, all counts refer to the current subsample. Lower Vmax⁡V_{\max} means a smaller worst-case departure from the global group proportions. We compare KCC and FKCC within each target ratio, where both methods use the same sampled objects and group proportions. Table R1 averages the ten-run means equally across the nine datasets.

Table R1. Clustering quality and group representation across the five target ratios.

Target RRMethodACCMNCEΔprof\Delta_{\mathrm{prof}} (×10−3\times10^{-3})Vmax⁡V_{\max}
1KCC0.74230.930924.0080.0979
1FKCC0.82570.98394.7130.0466
2KCC0.75070.909418.0050.0774
2FKCC0.82280.96084.2500.0433
4KCC0.73440.865919.0450.0723
4FKCC0.82870.94083.1030.0338
8KCC0.74460.809713.3090.0568
8FKCC0.81050.91172.4350.0253
10KCC0.74180.77745.9030.0491
10FKCC0.81480.90012.1380.0212

FKCC has higher mean ACC and MNCE and lower mean Δprof\Delta_{\mathrm{prof}} and Vmax⁡V_{\max} at every target ratio. Across the 45 dataset-ratio conditions, the ten-run means improve in all 45 for MNCE, Δprof\Delta_{\mathrm{prof}}, AvgTV, and Vmax⁡V_{\max}. ACC, NMI, and ARI improve in 41, 38, and 41 conditions, respectively, and FfairF_{\mathrm{fair}} improves in all 45. The group-representation gains therefore persist across the tested ratios, alongside improved clustering quality in most conditions.

The recorded FKCC objective trajectories for the 450 paired cases are all non-increasing; the maximum number of sweeps is 45. Table R2 compares optimization time and sweep counts at R=1R=1 and R=10R=10. We timed single-threaded FKCC optimization on an Intel Core i7-12700 CPU, excluding representation construction and initialization. Times are reported as mean ± standard deviation over ten repetitions.

Table R2. FKCC optimization time under group-size imbalance.

DatasetSamplesTime: R=1R=1 (ms)Time: R=10R=10 (ms)Mean sweeps: R=1R=1 → R=10R=10
CKD2200.476 ± 0.1970.386 ± 0.0852.6 → 2.1
COIL2070044.712 ± 11.66543.462 ± 13.2886.9 → 6.6
MFEAT100031.110 ± 7.50333.267 ± 5.9536.3 → 6.9
Billionaires6007.340 ± 2.7087.956 ± 3.1745.2 → 6.0
USPS3568100021.979 ± 7.91019.829 ± 7.4176.9 → 6.0
HAR3000315.123 ± 81.829312.689 ± 74.35814.1 → 13.9
Census100092.162 ± 20.60586.557 ± 43.07614.4 → 12.2
OULAD1000204.814 ± 100.475204.048 ± 116.11219.1 → 18.8
FairFace70006144.256 ± 1109.3935374.565 ± 1181.02431.9 → 27.2

The ratio of mean optimization time at R=10R=10 to that at R=1R=1 ranges from 0.811 to 1.084, with lower times on seven datasets and higher times on two. These measurements show no consistent slowdown as group sizes become more unequal.

AuthorsOpenReview ↗

Paired statistics and group-class association (2/2)

Q1. Paired statistics

Below, we report 95% confidence intervals for the mean paired differences (FKCC minus KCC) over the 90 matched trials (nine datasets, ten repetitions each). We used a hierarchical paired bootstrap with 200,000 resamples. In each resample, we drew nine datasets with replacement and ten paired runs with replacement within each selected dataset, then averaged the dataset-level differences with equal weight. The intervals below are the 2.5th and 97.5th percentiles of the bootstrap distribution.

MetricMean change, FKCC - KCC95% confidence interval
ACC+0.084966[0.050326, 0.120436]
MNCE+0.027181[0.007226, 0.057216]
FfairF_{\mathrm{fair}}+0.066857[0.040760, 0.094812]
Δprof\Delta_{\mathrm{prof}}-0.007719[-0.019261, -0.000171]
AvgTV-0.020740[-0.043142, -0.004352]

Positive differences indicate improvement for ACC, MNCE, and FfairF_{\mathrm{fair}}; negative differences indicate improvement for Δprof\Delta_{\mathrm{prof}} and AvgTV. All five confidence intervals exclude zero in the direction favoring FKCC.

We also applied an exact two-sided sign test to the nine dataset-level mean paired differences, using datasets rather than individual runs as the test units. All nine favor FKCC for each listed metric, giving an unadjusted p=0.0039p=0.0039. Applying Holm correction jointly to all five listed tests gives an adjusted p=0.0195p=0.0195 for each.

The revised Appendix B.1 also reports this paired statistical assessment.

Q2. Group-class association

We examined this on COIL20, MFEAT, and USPS3568, the three benchmarks with synthetic protected groups. Each dataset was evaluated at five association levels with ten matched repetitions per level. All objects and group totals were kept fixed. Within each repetition, the base partitions, input representation, and initial labels were also fixed; only the protected-group labels changed.

We interpolated the class-conditional group counts between approximately independent and strongly class-associated allocations, preserving the original group totals exactly after integer rounding. This separates changes in association from changes in group-size imbalance. We measured realized association as A=I(C;G)/H(G)A=I(C;G)/H(G), where CC is the ground-truth class and GG is the group label: A=0A=0 denotes independence, and A=1A=1 means group membership is fully determined by class. FKCC used the same quadratic weight and solver settings at every level.

The table reports the complete five-level sweep for each dataset. Entries are ten-run means, including the realized association AA. Differences are FKCC minus KCC, with ACC differences expressed in percentage points.

DatasetAAΔACC (pp)ΔMNCEΔFfair\Delta F_{\mathrm{fair}}
COIL200.0001+4.632+0.0629+0.0545
COIL200.0427+4.028+0.0657+0.0543
COIL200.1891+3.549+0.0996+0.0685
COIL200.4501+0.694+0.1902+0.1653
COIL200.9793-1.271+0.3809+0.4870
MFEAT0.0000+15.335+0.0170+0.0983
MFEAT0.0458+15.170+0.0261+0.0981
MFEAT0.1818+11.970+0.0869+0.1044
MFEAT0.4455+5.085+0.2471+0.1771
MFEAT0.9531-1.385+0.6013+0.6550
USPS35680.0000+10.607+0.0010+0.0723
USPS35680.0437+9.633+0.0108+0.0688
USPS35680.1802+3.799+0.0592+0.0566
USPS35680.4340-1.914+0.2049+0.1191
USPS35680.9356-7.427+0.5671+0.5579

Across the three datasets and five levels (15 experimental conditions), FKCC improves mean MNCE and FfairF_{\mathrm{fair}} in every condition and mean ACC in 11. Mean Δprof\Delta_{\mathrm{prof}} and AvgTV are also lower in all 15 conditions. At moderate association (AA approximately 0.18–0.19), ACC and MNCE improve together on all three datasets. At the strongest association level, the absolute results are:

DatasetACC, KCC → FKCCMNCE, KCC → FKCC
COIL200.6990 → 0.68630.0000 → 0.3809
MFEAT0.7656 → 0.75170.0095 → 0.6108
USPS35680.7971 → 0.72290.0704 → 0.6374

Across the tested association levels, FKCC's MNCE advantage over KCC grows, while its ACC advantage narrows and becomes negative at higher association. At the strongest association level, mean ACC is 1.27, 1.39, and 7.43 percentage points below KCC, respectively, while MNCE and FfairF_{\mathrm{fair}} remain higher. FKCC's absolute ACC and MNCE decline overall as association increases. When group membership closely follows class, retaining class structure and making cluster membership independent of group membership become competing goals. The experiment thus distinguishes simultaneous gains at moderate association from representation gains with an accuracy cost at strong association.

Reviewer_tnp6OpenReview ↗
Rating
3
Confidence
4
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

FKCC uses a consensus clustering objective in which the distortion coefficients depend on the current allocation of protected groups across clusters. Unlike fixed-weight clustering, moving an object changes not only the distortion terms but also the coefficients of the affected group–cluster cells. The authors handle this dependence through a center-eliminated formulation and a local-search algorithm based on sufficient statistics. The theoretical analysis examines allocation behavior under fixed distortions and explains the special role of quadratic weighting. It also establishes an exact finite–empirical identity, a stability bound, and uniform estimation results under a fixed-representation sampling model.

Critical strengths
  1. The motivation for allocation-dependent distortion is clear. Group allocation affects both the distortion contributed by each group–cluster cell and the distribution of protected groups across output clusters. FKCC incorporates this connection into the consensus objective through quadratic assignment-dependent coefficients, rather than adding separate fairness constraints or regularization terms. This distinguishes the method from conventional fixed-weight clustering and provides a meaningful approach to promoting group-representation fairness.

  2. The theoretical analysis is thorough and informative. The paper characterizes allocation behavior under fixed cell-average distortions and explains the special role of quadratic weighting within the positive-power family. It also establishes an exact finite–empirical identity for feasible induced assignments, a stability bound for the center-eliminated risk, and uniform estimation results under a fixed-representation sampling model.

Critical weaknesses
  1. Although the paper examines robustness to different base-partition generators, the sensitivity of the local-search solution to initialization is not analyzed separately. Given that the algorithm guarantees only a one-object local optimum, a controlled analysis with fixed base partitions would help clarify the stability of the final results.
Questions for authors
  1. The sensitivity analysis in Table 2 focuses on power-based allocation weights. How does quadratic weighting compare with other nonlinear weighting functions, such as normalized exponential or logarithmic weights?
  2. Is the stability result in Theorem 2 specific to quadratic allocation weighting, or can it be extended to other fixed power exponents?
  3. The experiments use 20 base partitions selected from a pool of 200 candidates. Could the authors clarify the selection procedure, including whether the partitions are sampled randomly or chosen according to a specific criterion?
2 comments
AuthorsOpenReview ↗

Initialization sensitivity and alternative weights (1/2)

We thank the reviewer for the constructive comments and provide our detailed responses below.

W1. Sensitivity to initialization

To isolate the effect of initialization, we fixed the first 20 base partitions and the remaining algorithm settings on each of the nine datasets, and varied only the random seed used for initialization. We reused the ten prespecified seeds from the main experiments, giving 90 runs in total. The table reports mean ± population standard deviation over the ten runs for the five metrics used in the paper, ACC, NMI, ARI, MNCE, and FfairF_{\mathrm{fair}}. Values are rounded to four decimal places.

DatasetACCNMIARIMNCEFfairF_{\mathrm{fair}}
CKD0.9449 ± 0.00000.7267 ± 0.00000.7909 ± 0.00000.9498 ± 0.00000.9473 ± 0.0000
COIL200.7059 ± 0.01780.8117 ± 0.00600.6738 ± 0.01270.8937 ± 0.10090.7860 ± 0.0424
MFEAT0.9238 ± 0.00020.8534 ± 0.00070.8400 ± 0.00050.9942 ± 0.00000.9577 ± 0.0001
Billionaires0.9629 ± 0.00000.8069 ± 0.00000.8570 ± 0.00000.9815 ± 0.00000.9721 ± 0.0000
USPS35680.9153 ± 0.00000.7573 ± 0.00000.7948 ± 0.00000.9987 ± 0.00000.9552 ± 0.0000
HAR0.7452 ± 0.08250.6720 ± 0.06840.5984 ± 0.06990.9877 ± 0.00480.8470 ± 0.0593
Census0.6225 ± 0.06100.0562 ± 0.05110.0748 ± 0.06580.9996 ± 0.00040.7654 ± 0.0456
OULAD0.7413 ± 0.00010.1749 ± 0.00010.2330 ± 0.00010.9780 ± 0.00000.8434 ± 0.0000
FairFace0.8608 ± 0.00000.4226 ± 0.00000.5207 ± 0.00000.9953 ± 0.00000.9232 ± 0.0000

With the base partitions fixed, FKCC shows good performance consistency across the tested seeds on most datasets, with standard deviations below 0.001 for all five metrics on six datasets. Some datasets still exhibit variation in clustering quality or fairness across seeds.

Q1. Comparison with other nonlinear weights

We compared quadratic weighting with normalized exponential and logarithmic weights, and included linear weighting as a reference. Each function uses ten matched runs on each of the nine datasets. We varied only the allocation-weight function and held the remaining experimental settings fixed.

f_{\rm exp}(p)=\frac{e^p-1}{e-1},\qquad f_{\rm log}(p)=\frac{\log(1+p)}{\log 2},\qquad f_{\rm lin}(p)=p.$$ All four functions satisfy $f(0)=0$ and $f(1)=1$. The table reports macro-averages across the nine datasets. | Weight function | ACC | NMI | ARI | MNCE | $F_{\mathrm{fair}}$ | |:---|---:|---:|---:|---:|---:| | Quadratic | 0.8364 | 0.5903 | 0.6037 | 0.9809 | 0.8998 | | Normalized exponential | 0.8292 | 0.5855 | 0.5960 | 0.9769 | 0.8937 | | Normalized logarithmic | 0.8245 | 0.5809 | 0.5885 | 0.9737 | 0.8894 | | Linear | 0.8254 | 0.5821 | 0.5906 | 0.9751 | 0.8905 | Quadratic weighting achieves the highest macro-average values across all five metrics in this comparison. For fixed positive cell-average distortions, quadratic weighting yields the explicit allocation response $p_{tq}^{\star}\propto\bar\ell_{tq}^{-1/2}$. The quadratic coefficient aggregate also admits the exact squared-Euclidean decomposition analyzed in the paper. The empirical results and these structural properties support the quadratic choice used by FKCC.
AuthorsOpenReview ↗

Stability and base-partition selection (2/2)

Q2. Stability for other fixed power exponents

Yes. The stability argument extends to every fixed, prespecified exponent α≥1\alpha\ge1. Let RαR_\alpha be the center-eliminated risk obtained by replacing the quadratic weight by ptqαp_{tq}^{\alpha}. Set μq,α=∑tρtptqαmtq\boldsymbol\mu_{q,\alpha}=\sum_t\rho_t p_{tq}^{\alpha}\boldsymbol m_{tq} and βq,α=∑tρtptqα+1\beta_{q,\alpha}=\sum_t\rho_t p_{tq}^{\alpha+1}. The same admissibility conditions as in Section 4.2 imply ∥μq,α∥2≤Bβq,α\lVert\boldsymbol\mu_{q,\alpha}\rVert_2\le B\beta_{q,\alpha} and, for βq,α>0\beta_{q,\alpha}>0,

0≤∥μq,α∥22βq,α≤B2βq,α.0\le\frac{\lVert\boldsymbol\mu_{q,\alpha}\rVert_2^2}{\beta_{q,\alpha}}\le B^2\beta_{q,\alpha}.

The ratio therefore has the continuous extension zero at βq,α=0\beta_{q,\alpha}=0. Parameterizing the proof of Theorem 2 gives

\le\sum_t\rho_t\Big[ (4\alpha+1)B^2\lVert\boldsymbol p_t-\boldsymbol p'_t\rVert_2 +\lVert\boldsymbol s_t-\boldsymbol s'_t\rVert_2 +2B\lVert\boldsymbol M_t-\boldsymbol M'_t\rVert_F \Big].$$ The ratio and additive distortion terms contribute $3\alpha+1$ and $\alpha$, respectively. At $\alpha=2$, the coefficient $4\alpha+1=9$ recovers the quadratic estimate. Thus, stability holds more broadly for fixed $\alpha\ge1$, whereas the exact squared-Euclidean coefficient decomposition across arbitrary cluster counts singles out $\alpha=2$ within the positive-power family. **Q3. Selection of the 20 base partitions** For repetition $r\in\\{1,\ldots,10\\}$, the 20 input partitions are columns $$20(r-1)+1,\ldots,20r$$ of the stored 200-partition pool: columns 1–20 in the first repetition, 21–40 in the second, and so on through 181–200 in the tenth. These are prespecified, disjoint blocks, and block selection uses no clustering-accuracy, MNCE, or other performance criterion. The indices make the input block for each repetition directly reproducible. The candidate pool is generated by coordinate-descent k-means, with base-cluster counts sampled from $[k,\lceil\sqrt n\rceil]$ as stated in Section 5.1. This generation-stage randomness is separate from the fixed block indices, which uniquely determine the input partitions for each repetition from the stored pool. The revised Appendix A.2 specifies this base-partition selection rule.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Summary of Paper Contributions and Rebuttal Responses

We sincerely thank you and the reviewers for your careful assessment and constructive feedback. We summarize the paper's contributions and rebuttal evidence below; details appear in our point-by-point responses.

1. Paper Contributions

Fair clustering ensembles aggregate base partitions while accounting for protected-group representation. Group representation and consensus fitting are linked by the same output assignment. Building on their shared dependence on group allocation, we study how group representation and fitting distortion interact, and how this interaction shapes allocation behavior and cross-group representation. FKCC realizes this through allocation-dependent distortion: each group–cluster distortion is weighted by the square of the group's conditional allocation proportion, without hard profile-alignment constraints or a separate fairness penalty.

We characterize this mechanism theoretically. With fixed positive mean group–cluster distortions, the mass-only allocation objective is linear, whereas quadratic weighting yields a strictly convex continuous allocation problem with a unique inverse-square-root response. Groups with proportional distortion profiles thus have identical, potentially nonuniform optimal allocations despite different absolute fitting difficulties; approximately proportional profiles admit a quantitative discrepancy bound.

Positive-power weights more generally yield responses determined by relative distortions. Quadratic coefficients additionally admit an exact decomposition: the group-weighted sum of squared allocation proportions equals group-profile discrepancy plus marginal cluster-mass nonuniformity and 1/k. Within the positive-power family, only the quadratic exponent preserves this squared-Euclidean decomposition for arbitrary cluster counts. For the complete objective, exact finite constructions establish instance-dependent effects on group-profile discrepancy, while a sharp pointwise bound applies under positive mean distortions in occupied cells.

For the nonseparable objective, exact center elimination and group–cluster sufficient-statistics updates enable monotone one-object coordinate descent with finite termination at a one-object local optimum. We establish an exact finite–empirical risk identity for feasible induced assignments, denominator-free stability, and uniform estimation under fixed-representation sampling assumptions. Nine-dataset experiments, including external baselines and 90 matched KCC–FKCC trials, support gains in clustering utility and group representation.

2. Summary of Rebuttal Responses

Reviewer tnp6 — initialization, weighting, and stability. With base partitions fixed, six of nine datasets had standard deviations below 0.001 on all five metrics across ten initialization seeds. Quadratic weighting achieved the highest macro-averages on all five metrics versus normalized exponential, logarithmic, and linear alternatives. We extended stability to each prespecified fixed exponent α ≥ 1 and clarified ten disjoint 20-partition blocks from 200 base partitions, selected without performance screening.

Reviewer 2XtJ — reliability and group structure. We conducted 450 matched trials across five target group-size ratios. All four representation measures favored FKCC in the ten-run means of all 45 dataset–ratio conditions; mean ACC improved in 41, with no consistent slowdown as group-size imbalance increased. For the original 90 trials, 95% confidence intervals from a hierarchical paired bootstrap favored FKCC on five metrics; Holm-adjusted dataset-level sign tests yielded p = 0.0195. Group–class association experiments showed joint accuracy and representation gains at moderate association, but an accuracy trade-off at the strongest tested level. We disclosed corrected KCC reference values in Tables 9–10 and Figures 1 and 3; FKCC results and main conclusions remain unchanged.

Reviewer ZCL6 — independent-reference evaluation. We clarified that the finite–empirical identity applies to feasible induced assignments, while uniform estimation assumes a representation rule fixed independently of aggregation objects. We then ran ten independent-reference splits on each of nine datasets. Preprocessing parameters, base clustering models, and the representation rule were fitted on reference objects alone and frozen before encoding aggregation objects. With matched representations and initial assignments, FKCC achieved higher mean ACC, ARI, MNCE, and FfairF_{\mathrm{fair}} on all nine datasets and higher mean NMI on eight, while reducing profile discrepancy and AvgTV on all nine. These results indicate that the gains persist when representation construction is separated from consensus aggregation, providing evidence in a setting closer to the fixed-representation sampling model.

We appreciate your consideration of these contributions and new evidence.

Sincerely,

The Authors

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.