acceptodds
Under review as a conference paper at ICLR 2027

Proportional Hierarchical Clustering

Abstract

Hierarchical clustering represents data at multiple levels of granularity, but proportional fairness is traditionally only defined for a single partition. We therefore study how it can be extended to an entire hierarchy. Building on prior work on proportional clustering, we introduce two notions: the local core, which requires proportional fairness at each split, and the global core, which requires it at every partition in the hierarchy. We study both notions under the maximum loss and average loss objectives, where an agent’s loss is, respectively, the maximum or average distance to other members of their cluster. We show that the two core notions are incomparable and that standard agglomerative clustering techniques fail to satisfy them. However, under the maximum loss objective, a hierarchical clustering in the local core always exists. On the way, we resolve an open question from Caragiannis et al. (2024) by showing that there always exists a non-centroid clustering in the core for k = 2, whereas for k ≥ 3 the core can be empty (even for Euclidean distances). For the global core, we show that even arbitrary approximations of it need not exist. However, doubling the coalition size threshold allows us to compute an outcome in the global 16-core for maximum-loss and global 8n-core for average-loss, where n is the number of data points.

Primary area:
learning theory
Keywords:
hierarchical clustering, proportional fairness, core stability, non-centroid clustering

Reviews

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

The paper studies proportional fairness in hierarchical clustering. Instead of requiring fairness for one partition into k clusters, it considers whether an entire hierarchy can satisfy proportional fairness.

The authors introduce two notions:

  • Local core: Every binary split must be proportionally fair within its parent cluster.
  • Global core: Every k-clustering appearing in the hierarchy must satisfy proportional fairness, with blocking coalitions of size at least n/k. They consider two agent-loss functions: maximum distance to another cluster member and average distance to cluster members.

The distinction between the two core notions is meaningful. The paper also addresses an open problem concerning the existence of non-centroid core-stable clustering for k=2.

Critical strengths

Resolving the existence question for non-centroid k=2 clustering is interesting independently of hierarchical clustering.

Critical weaknesses

The algorithmic result still remains open while the paper proves existance for 2-clustering.

There are no experiments!

Questions for authors

Is the factor 2 in the coalition-size threshold necessary to obtain any constant-factor approximation?

Do you have any algorithms that you think will work well on the 2-clustering case?

Can you add some experiments on tadesoffs of fairness vs. quality of clustering?

1 comment

Official comment answering Reviewer ALc7

Thank you for your feedback.

Coalition size threshold for global core

We address this question in the global official comment above.

Algorithms for 2-Clustering

With the maximum loss objective, the GreedyCapture algorithm by Caragiannis et al. yields a non-centroid clustering in the 22-core. Applying it recursively thus gives a hierarchy in the local 22-core. Finding an exact core-stable 22-clustering efficiently remains open.

Empirical evaluation

Please refer to our answer in the global official comment above.

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

The paper synthesizes the literature on proportional fairness and fair hierarchical clustering, specifically considering how to construct locally and globally fair hierarchies (as well as the tension between the two). In constructing the algorithms that yield local cores, the authors show that agglomerative techniques must fail and instead devise recursive procedures for ensuring local constraints hold. Yet, they further show that such local core constructions cannot be made global without a further relaxation to the size of "defecting" populations.

Critical strengths
  • The paper is written very clearly, all results are well motivated, algorithms are intuitively sketched, and proof sketches are sensible.
  • Proper engagement with the literature on clustering and its many fair variants, and clear intuition building towards why the 2-clustering technique was used based on failures of agglomerative clustering approaches.
  • Clean, novel, extensions on the "core" for proportional fair hierarchical clustering which reveal an interesting tension between local and global core notions for hierarchies.
Critical weaknesses
  • In Theorem 9, the global core approximation for the average-loss objective yields an (α=8n,δ=2)(\alpha = 8n, \delta = 2)-core. Because the loss approximation factor α\alpha scales linearly with the dataset size nn so this guarantee becomes practically vacuous for large datasets
  • As a result of the above, some empirical validation would be appreciated to examine the merits of this method in practice.
  • The k=2k=2 resolution to Caragiannis open problem is existential, not constructive.
Questions for authors
  • Since Theorem 3 relies on the PPAd-complete Scarf's theorem followed by bipartite conflict-graph rounding lemma, does the structure of the conflict graph suggest a direct polynomial-time combinatorial algorithm for finding a core-stable 2-clustering under maximum loss? or is there a barrier?
  • Theorem 8 shows that no finite \alpha-approx global (α,1\alpha,1)-core exists and ScoopNOrder achieves (16,216,2)-core, so can the impossibility result be extended for some δ>1\delta > 1 (ie. between $\delta =1 $ and 2 used for these two results)?
1 comment

Official comment answering Reviewer Rb61

Thank you for your feedback.

Empirical evaluation

Please refer to our answer in the global official comment above.

Polynomial-time algorithm for 2-Clustering

We have thought about it, but were not able to use the conflict graph argument directly. Of course, given the loss vector of a fractional solution, we can construct and bipartition the conflict graph in O(n2)O(n^2) time.

Coalition size threshold for global core

We address this question in the global official comment above.

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

The paper introduces the concept of proportional fairness into hierarchical clustering. Therefore, the authors extend the α\alpha-core definitions to hierarchies: global core and local core. The remainder of the paper then mostly covers theoretical results on those defined core concepts. The proposed algorithm ScoopNOrder then shows how one can construct a hierarchy while preserving the properties of global and local core.

Critical strengths
  • The authors extended the concept of fairness to hierarchies and stated theoretical theorems regarding fairness / local and global core properties.
  • The paper shows for the open problem of Caragianis et al. that there always exists a 2-clustering in the core under the maximum-loss objective.
Critical weaknesses
  • The paper is only stating theoretical results and doesn't show any practical applicability. This is especially impractical for a paper on fairness.
Questions for authors

Question:

  • Do you have experimental results / a case study for the theoretical results?
  • Line 228: Does Ward’s method, average and complete linkage also fall into the "standard linkage function" category and Theorem 1 applies to them? What defines a "standard" linkage function?
  • What is the price for using ScoopNOrder? E.g., Dasguptas tree cost of having a "fair" tree.

Minor questions / Comments:

  • What is the runtime complexity of algorithm 1?
  • Footnote 2, I would avoid reusing the variable δ\delta again in a new setting.
  • Line 956: probably typo in upper bound. instead of "= loss$_i$(C)" it probably should be "≤\leq loss$_i$(C)"
3 comments

Official comment answering Reviewer 8K49

Thank you very much for your feedback and your minor comments.

Empirical evaluation

Please refer to our answer in the global official comment above.

Ward's method

Our definition of a "standard linkage function" requires $\min_{a\in A,b\in B} d(a,b) \leq f(A,B) \leq \max_{a\in A,b\in B} d(a,b)$, so single, average, and complete linkage fall into this category. Ward's method can violate these bounds. However, the counterexample extends to Ward, as it necessarily produces the same prefix-merging hierarchy used in Theorem 1. More specifically the proof only compares clusters occupying disjoint intervals on the line. For such clusters, it suffices that min⁡a∈A,b∈Bd(a,b)≤f(A,B)≤cmax⁡a∈A,b∈Bd(a,b)\min_{a\in A,b\in B} d(a,b) \leq f(A,B) \leq c\max_{a\in A,b\in B} d(a,b) for some c<αn+1c<\alpha n+1. Ward's linkage height satisfies these bounds with c≤n/2c\le\sqrt{n/2}, while centroid, median, weighted and minimax linkage satisfy them with c=1c=1. We will clarify this distinction and include the argument.

Price for using ScoopNOrder in terms of Dasgupta's cost

We have not yet analyzed ScoopNOrder's Dasgupta cost in general. A small line example already shows that a better core guarantee can mean a lower objective value. Consider the points −4,−1,1,11-4,-1,1,11 on a line. For the distance-based version of Dasgupta's objective from Cohen-Addad et al. the best tree has value 176176, and any global (α,1)(\alpha,1)-core tree under maximum loss with α<3/2\alpha<3/2 has value at most 154154, which is 78\frac{7}{8} of the optimal value. ScoopNOrder returns an exact-core tree of value 154154 here. We would like to study this tradeoff more closely in follow-up work, both in theory and in experiments.

Running time of Algorithm 1 (ScoopNOrder)

Given the distance matrix, Algorithm 1 can be implemented in time O(n2log⁡n⋅(1+Δ))O(n^2\log n \cdot (1+\Delta)) time and O(n2)O(n^2) space, with Δ=⌈log⁡4(2diam⁡(N))⌉\Delta=\lceil\log_4(2\operatorname{diam}(N))\rceil being the variable from the algorithm itself. We have Δ+2\Delta+2 radii, O(log⁡n)O(\log n) levels, and nn candidate centers. By storing cluster-to-center maximum distances we can compute each scan in time O(n)O(n). Since cluster sizes are powers of two during the main loop, we can check feasibility by summing the sizes of eligible clusters smaller than the target. There are at most n−1n-1 scoops, so these steps take O(n2log⁡n)O(n^2\log n) time in total. Updating the stored maximum distances takes O(n2)O(n^2) time overall, and the final tree ordering takes O(nlog⁡n)O(n\log n). We will add this runtime analysis. We note that the Δ\Delta factor can also be replaced by n2n^2 in the analysis, since there are at most O(n2)O(n^2) distinct distances between the points.

Further minor comments

Thank you for pointing this out. We will fix footnote 2 and the typo in the equation accordingly.

Thank you for the clarifications!

I still think that fairness is not a complete theoretical construct, and to assess the method clearly, some "fairness experiments" should be added. Hence, I'll keep the "weak accept" score.

We thank the reviewer for their reply and positive assessment. We would like to emphasize that we, too, consider an empirical evaluation important. As pointed out in our official comment, we plan this for future work, together with work on the auditing problem, which is a prerequisite for meaningful experiments.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.