acceptodds
Under review as a conference paper at ICLR 2027

Proportional Clustering: Verification and Optimal Selection

Abstract

We study the problem of proportional clustering. When clustering is used to select representatives, keeping each point close to a center does not ensure that large groups receive a proportional share of the centers. We ask when this proportionality can be checked exactly and when it can be imposed while still optimizing the clustering objective exactly. We consider metric proportional justified representation (mPJR) and its stronger variant mPJR. In arbitrary metrics, we reduce exact mPJR verification to maximum flow; the same test computes the largest number of missing centers and, through a finite search, the smallest dilation of representation distances under which mPJR holds. On the real line, we show that proportionality and clustering loss share an interval structure. As a result, a single minimum-cost flow finds an optimal weighted discrete -median or -means selection subject to mPJR, and also makes an existing selection proportional with the fewest replacements. In contrast, verifying mPJR is already coNP-complete in four-dimensional Euclidean space. With exact optimization, the cost of proportionality relative to the unconstrained optimum can still be arbitrarily large, even on the line. Experiments on synthetic populations and model confidence scores separate the cost of mPJR from the additional cost of mPJR and from the cost of retaining existing centers.

Primary area:
alignment, fairness, safety, privacy, and societal considerations
Keywords:
proportional clustering, verification

Reviews

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

The paper works on some formulations of proportional clustering and they obtain the following results:

  1. They prove that mPJR+ (He 2026, arXiv May 26), a stronger version of the original problem (mPJR), can be verified in polynomial time via flow techniques.

  2. The authors proved that mPJR (the original problem) can be optimized in polynomial time, in terms of the k-medians/k-means objective, when the points lie on the real line.

  3. The verification of mPJR is coNP-Hard in R4R^4, improving the coNP-hardness for metric spaces established by (He 2026, Arxiv May 26).

They also present experimental results

Critical strengths
  • The optimization of the k-medians and k-means for the line (mPJR) is novel, as far as I can tell, and interesting.
Critical weaknesses
  • The concept of proportional clustering seems reasonable; the idea is trying to ensure that large groups have more (good) representatives than small groups. However, it is unclear why the proportionality conditions mPJR and its variant (mPJR+), addressed in the paper, capture the concept of proportionality well; they are not intuitive to me. In the definition of mPJR, an ℓ\ell-cohesive group must have ℓ\ell candidates close to every member, but mPJR only guarantees ℓ\ell selected centers that are each close to at least one member. The paper does not sufficiently explain why this weaker guarantee is appropriate for capturing clustering proportionality. Maybe this is justified in the existing literature, but from the discussion presented in the body of the paper, I'm not very convinced.

  • Limited novelty and significance relative to previous work.
    The novelty and significance of the contributions seem somewhat limited when taking previous results into account. In my assessment, the most novel result is the polynomial-time optimization of the clustering objective subject to mPJR. However, the algorithm only works on the real line, which limits its applicability. The flow-based verification of mPJR+ appears incremental relative to the polynomial-time verification established by He et al. (2026) and the min-cut approach for PJR+ developed by Springham (arXiv, 2026), although the paper includes some extensions such as support for weights and the computation of representation deficits. Finally, the strengthening of the existing coNP-hardness result to R4\mathbb{R}^4 is interesting, but I do not find it particularly compelling for the ICLR audience.

Questions for authors

Could you explain in an intuitive way why mPJR and its variants are suitable formulations to capture clustering proportionality?

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

This paper considers proportional clustering under mPJR and mPJR+. Given a set of n points and a set of m potential centers, and a prespecified parameter k, the goal is to select k out of m centers such that proportional representation is satisfied as defined below. Let q=n/k.

mJPR: asks that for any radius r, and any level l=1,...,k, and any group S of at least lq points, if at least l candidates are within distance r of every member of S, then at least l selected centers must each be within distance r of a member of S.

mJPR+: asks that for any radius r, and any level l=1,...,k, and any group S of at least lq points, if there is an "unselected" candidate center that is within distance r of every member of S, then at least l selected centers must each be within distance r of a member of S.

In the weighted setting, each point has its own weight and the quota is the total weight divided by k.

This paper makes the following contributions:

  • The prior work on this problem does not consider "optimizing k-means/k-median" cost while satisfying this fairness constraint. This work considers the optimization version for the first time. However it only gives a solution to the problem on the "line" metric (where all points and candidate centers lie on the real line) using min-cost flow.

  • They also consider the "verification" variant of the problem (where we only need to check if a given solution satisfies the fairness constraint) which uses max flow. The problem was already shown to be verifiable using submodular maximization (at least in the unweighted setting).

  • They show the cost of proportionality is unbounded.

  • They show that the problem remains coNP-complete even in 4 dimensional Euclidean space (it was previously known for general metrics).

  • Finally, they show experiments to examine the cost of proportionality, the additional cost of mPJR+, and the effect of keeping existing centers.

Critical strengths

The proportionality notion of fairness is interesting and that it is very general (should hold for all sets, and all radii) at the same time and does not require a pre-labeling of the data set.

The paper is well-presented and I did not detect any error in the paper.

They look at both upper and lower bound for the problem and have experiments.

Critical weaknesses

I see the overall contribution of this paper as not sufficient for ICLR. I would have given it a higher score if the paper was considering the optimization version in general metrics even if it was an approximate solution. But currently the general metric verification and the lower bound is marginal in compare to prior work and the line case is very specialized and may not be of broad interest to ICLR audience.

Questions for authors
  • Did you try approximating the clustering cost in general metrics? e.g. find a solution that is approximately optimal in compare to the best fair clustering solution.
  • Can you clarify if the prior work of He et al verification result work for the weighted setting (or it is easy to extend it to the weighted case)?
Reviewer_t45XOpenReview ↗
Rating
1
Confidence
2
Informativeness
1
Presentation
1
Soundness
2
Read review
Paper summary

The paper introduces algorithms for the Metric proportional justified representation (mPJR) and mPJR+ problem. In the mPJR problem, we are given n data points and m candidates and want to select k centers X among the m candidates in a way that a proportionality condition is satisfied. In particular, for every subset S of data points and for all radii r, if S contains at least a ℓ/k\ell/k-fraction of all data points (or that fraction of the total weight in a weighted instance) and there are at least ℓ\ell candidates in the intersection of all Balls with center a data point in S and radius r, then there must be at least ℓ\ell candidates in X with distance at most r from some point in S. mPJR+ is a stronger variant of mPJR and the authors also define mPJR+ with distance dilation γ≥1\gamma\geq 1 (γ=1\gamma = 1 corresponds to mPJR+). The paper studies several types of problems. The verification problem asks to verify whether a given solution X satisfies the proportionality condition. The authors also are interested in finding the minimum number of replacements to an invalid solution X to make it satisfy the proportionality condition. Another type of problem is computing an mPJR solution X. Some of the main results are summarized below:

  1. mPJR+ can be verified in any metric with at most (m-k) n maximum flow computations.
  2. An algorithm is introduced that solves mPJR for the special case where the points and candidates lie on a line. The algorithm computes the minimum cost solution X that satisfies the proportionality condition for common objectives like k-means or k-medians.
  3. The authors prove that, given a solution X it is hard (in particular co-NP complete) to verify mPJR, even for low-dimensional spaces. Moreover, given X and a level ℓ\ell, it is co-NP complete to verify mPJR+ for this level even for low-dimensional spaces.
Critical strengths
  • None.
Critical weaknesses

The paper is very hard to read. Here are some examples that support this opinion.

  1. Section 3 is very hard to read and is presented in an unorthodox way. Lines 204-223 are very dense and should be part of the proof of Theorem 3.1 and not presented before the theorem and complete the other half of the proof in the appendix. These lines are also hard to follow. For example, in the network specification, the domains of i and x are not even stated and are only implied.
  2. In line 233, it reads: "The algorithm is strongly polynomial with a strongly polynomial maximum-flow method, such as that of Orlin (2013)." However, the pseudocode of the algorithm is never explicitly stated, making the text rough to read.
  3. The Our Results section is hard to read. Lines 071-074 give a vague and hand-wavy description of their ideas, using phrases like "missing representatives", "group with the greatest shortfall", "distance dilation" and others that are not defined up to this point. Line 074 reads: "These quantities measure how many centers a group lacks and how much farther it must reach." trying to explain these undefined terms, with no success, as this sentence is hand-wavy itself.
  4. There is not enough discussion that highlights the main technical contributions in comparison to prior work (for example Theorem 3.1. compared to Springham 2026).

In conclusion, the paper would benefit from a more detailed explanation of the contributions and proof ideas, presented in a clear and understandable way.

Questions for authors

I have no questions whose answers can affect my assessment.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.