WorksComputer Science
How Much Distribution Shift Can a Clustering Withstand? Exact Split and Merge Certificates for Structured Transports
Abstract
In clustering, the distribution of the population being clustered is often uncertain or changes over time, so the true distribution may shift away from the nominal distribution used to form the clustering. Once the clustering is committed and each member is assigned to a cluster, such shifts may change the distribution of each cluster. They can make a cluster too spread out for one representative at a given resolution, motivating a split, or bring distinct clusters close enough to share a representative at that resolution, motivating a merge. We make these split and merge events precise using a local stability criterion built on the phase-transition analysis in deterministic annealing. This notion of stability enables us to quantify how robust a clustering is against such events. Furthermore, motivated by applications in which uncertainty and population change are structured, we study shifts whose displacements are restricted to a prescribed subspace. The smallest structured shifts that reach the respective thresholds define the split and merge radii, for which we obtain exact semidefinite programming (SDP) reformulations. The split SDP has only two scalar decision variables. These convex reformulations enable us to combine the radii into a robustness certificate for the full clustering that gives the size of the smallest structured shift that reaches any monitored split or merge threshold.
Introduction
Clustering addresses a fundamental problem: how to represent or serve a population effectively with a limited number of representatives. This problem arises in applications ranging from data compression and learning to sensor coverage and resource allocation (Rose, 1998; Mavridis and Baras, 2023b,a; Cortes et al., 2004; Sharma et al., 2008; Bayati et al., 2025). A clustering partitions points in into groups, each summarized by a representative or assigned a shared model, controller, or resource. The quality of this representation is commonly measured through distortion, typically defined as the average squared Euclidean distance between members and their representatives.
Once a clustering is committed, uncertainty in the original data (e.g., measurement errors) or later changes in the population may cause its distribution to differ from the nominal distribution used to form the clustering. We call this difference a distribution shift. Such a shift may change the number of representatives the population needs. A cluster may become too dispersed for one representative, motivating a split, or several clusters may come close enough to share one, motivating a merge. These revisions can incur both operational and computational costs: splitting may require additional resources, merging may require reconfiguring assignments or shared models, and finding a new globally optimal clustering is generally NP-hard [1]. It is therefore valuable to ask in advance: How much distribution shift can a labeled clustering withstand before a split or a merge is warranted?
To make this question precise, we must account for resolution: the number of representatives a population needs depends on the resolution at which it is viewed. At a coarse resolution, one representative may suffice for the entire population, whereas at a fine enough resolution, each distinct member of a finite population may need its own. Between these extremes, critical resolutions mark where a cluster splits into finer clusters or where several clusters merge into one. One way to formalize this notion of resolution is through deterministic annealing (DA), which uses a temperature parameter to balance distortion against the entropy of cluster assignments [19, 21]. The resulting objective is called the free energy. At sufficiently high temperatures, coincident representatives at the population mean form a local minimum of the free energy, resulting in a single effective cluster. As decreases, the resolution increases, and the coincident configuration undergoes a bifurcation at a critical temperature. Just below this temperature, the configuration becomes a saddle point, and separating the representatives along certain directions lowers the free energy, allowing distinct clusters to emerge and reveal finer structure in the population [19]. We refer to this local behavior as the stability of a distribution at temperature (Definition 1), which we apply to individual clusters and to collections of clusters.
To assess a given clustering without changing its assignments, we keep cluster labels attached to population members as the distribution shifts, preserving each cluster’s mass. At a fixed temperature , a distribution reaches the stability threshold when is its critical temperature. A split event occurs when a shift brings a cluster’s initially stable distribution to this threshold, and a merge event occurs when a shift brings a specified collection’s initially unstable pooled distribution to it. The events to monitor, for example splits of selected clusters or only pairwise merges, are prescribed by the application. For squared Euclidean distortion, Rose’s phase-transition analysis [19] gives the second-order stability criterion , where is the covariance of the distribution , with equality defining the stability threshold. This criterion involves only the covariance of the distribution being tested, so it can be used to assess a clustering regardless of how that clustering was obtained.
Quantifying the distance to a stability threshold requires specifying which population shifts are allowed and how their magnitude is measured. We measure a distribution shift by the square root of the smallest expected squared Euclidean displacement needed to transport the nominal distribution to the shifted distribution. Without restrictions on the displacements, this is the 2-Wasserstein distance [18].
In many applications, shifts are structured. For instance, disturbances and attacks in cyber-physical systems act through specific actuator or sensor channels [9], changes in feature vectors may affect only selected attributes while others remain fixed [22], and adversarial image perturbations may be restricted to a low-frequency subspace [12]. We model this structure by requiring displacements to lie in a prescribed linear subspace , with recovering unrestricted shifts. The split radius and merge radius are the smallest structured shifts, measured by this transport distance, that reach the respective events. These radii quantify the robustness of individual clusters or collections to specific events. To assess the clustering as a whole, we combine them into an overall robustness measure. Here, we adopt a worst-case approach: we define a transport distance for the entire labeled population and use the distance to the nearest monitored event as a robustness certificate. Every smaller structured shift is guaranteed to avoid all monitored events.
Such a certificate can also help compare candidate clusterings before deployment. Figure 1 compares two clusterings of the same population with identical nominal distortion. Under horizontal shifts at the same temperature, A’s split radius is more than three times B’s, revealing a substantial difference in robustness that distortion alone cannot capture. Comparing certificates across choices of shows how a clustering’s robustness depends on the allowed displacement directions.
Figure 1. Two clusterings of the same population with identical distortion need very different horizontal shifts to reach the split threshold. (a), (b) Candidate clusterings A and B; stars mark the cluster centroids. (c), (d) Minimum-cost horizontal shifts that bring one cluster in each clustering to the split threshold at the same ; grey shows the nominal cluster and the split direction. The threshold is reached when the covariance ellipse, with longest semiaxis , touches the dotted circle of radius . (e) Histograms of point displacement magnitudes under the shifts in (c) and (d); each split radius is the corresponding root-mean-square displacement.
Structured shifts introduce a geometric difficulty: restricting displacements to does not restrict the direction of instability to (notice how is not aligned with in Figure 1(c)). Displacements within can change the variance along directions with components in both and , so the structured problem cannot generally be solved by projecting the unrestricted problem onto . However, these displacements leave each point’s component in unchanged. Thus, a collection whose variance along some direction in already exceeds the threshold cannot reach the merge threshold at any transport budget. An initially stable cluster, on the other hand, can always reach the split threshold when .
For fixed and , we show that each event radius depends only on the covariance of the tested cluster or pooled collection. Our contributions are fourfold:
Exact moment reduction. We reduce the split and merge radius problems from optimization over infinite-dimensional structured transport plans to finite-dimensional optimization over the displacement covariance and the cross-covariance between nominal points and their displacements. The reduction is exact: every feasible pair of moments is realized by a structured transport plan. The results hold for arbitrary nominal distributions with finite second moments.
Split radius. For each feasible direction, we derive the minimum structured transport cost needed to reach the split threshold along it. Although minimizing this cost over directions is nonconvex, we compute the squared split radius through an exact SDP reformulation with two scalar decision variables. We recover an optimal split direction and construct an attaining structured transport plan.
Merge radius. For a specified collection of clusters, we formulate the squared merge radius as an exact SDP. We show that a merge is feasible if and only if the nominal pooled distribution has variance at most along every direction in . Whenever this condition holds, a deterministic affine structured transport map attains the minimum cost.
Clustering certificate. We define a label-preserving structured transport distance on clusterings and show that the distance to the nearest monitored event equals the minimum of the event radii, each scaled by the square root of the affected population mass. If this certificate is finite, an attaining
distribution shift exists which can cause at least one of the monitored events to happen, provided its corresponding transport budget.
Related work. The interpretation of DA temperature as resolution is also used by Srivastava et al. [21] to assess clusterings through the range of resolutions over which they persist, and by online DA methods to progressively increase model complexity (Mavridis and Baras [15]). While these works vary the resolution, we ask a complementary question: with the clustering and resolution fixed, what is the smallest distribution shift that reaches a split or merge threshold?
Resampling stability asks whether rerunning an algorithm on a new sample produces the same partition ([5] (von Luxburg 2010)), and perturbation stability assumes that an optimal clustering must remain unchanged under bounded multiplicative perturbations of pairwise distances ([2]). Our certificate concerns prescribed split and merge events for a given labeled clustering, without requiring optimality or rerunning the algorithm.
Wasserstein distributionally robust optimization (DRO) chooses decisions that minimize worst-case expected cost over a Wasserstein ball ([17, 11]). For -means clustering, Malik et al. [13] use this framework to design representatives that minimize worst-case distortion under a prescribed shift budget. We instead assess a given clustering and quantify its robustness, rather than designing representatives.
Our use of displacement covariances and cross-covariances between nominal points and their displacements is related to moment formulations in covariance steering ([7, 3]). Our setting differs from transport between spaces of unequal dimensions ([16]), as both nominal and shifted distributions lie in , while their displacements are restricted to a subspace . Lastly, our transport plans preserve cluster labels and each point’s component in . The resulting distance is therefore a conditional Wasserstein distance in the sense of Chemseddine et al. [6], conditioned on the label and the unchanged orthogonal component.
Notation. Vector norms are Euclidean, is the identity matrix, and denotes the real symmetric matrices. For , is the largest eigenvalue of , and means that is positive semidefinite. We denote the Moore–Penrose pseudoinverse by . For a set , denotes its power set, the collection of all subsets of . The set consists of probability distributions with finite second moments; and denote the mean and covariance of . For , denotes the set of couplings, or transport plans, of and , i.e., probability distributions on with first marginal and second marginal . The squared 2-Wasserstein distance is
Background and Problem Formulation
Clustering and free energy. Squared-error clustering chooses representatives to minimize the distortion , corresponding to assigning each point to one (the nearest) representative. Deterministic annealing (DA) replaces these binary assignments with probabilities and subtracts times their entropy. Minimizing the resulting free energy ([19]) over the assignment probabilities gives
As , converges to , uniformly in . (see Appendix § 6).
Following the DA formulation, we fix a temperature to specify the resolution and use the free energy to decide when a single representative at the mean is locally optimal for a distribution. Concretely, for , we place representatives at and ask whether slightly separating them lowers the free energy (2). This coincident configuration is always first-order stationary, i.e., (Appendix § 9.§ 1), so we examine its Hessian.
Definition 1 (Stability). At temperature and for any , a distribution is stable if , unstable if this Hessian has a negative eigenvalue, and critical if it is positive semidefinite but singular (we call it critical because is then its critical temperature).
This classification does not depend on (see Lemma 2), and critical distributions are exactly those at the stability threshold.
A split event occurs when an initially stable cluster distribution reaches the stability threshold, and a merge event occurs when the initially unstable pooled distribution of a collection reaches it. Both events include critical distributions, since an arbitrarily small (unrestricted) perturbation of a critical in the 2-Wasserstein sense can make it stable (e.g., a contraction about its mean) or unstable (e.g., an expansion). The covariance criterion in Lemma 2 makes this clear.
To determine which shifts can reach these thresholds and at what cost, we first define structured transport plans. Let be a prescribed linear subspace with . A transport plan is -structured if its displacements lie in almost surely. For , define
and the structured transport distance
the least cost of transporting to with -structured plans. We use the convention ; for , . The distance is finite if and only if and have the same marginal on , and if so, an optimal plan exists. When the marginals agree, is the conditional Wasserstein distance of Chemseddine et al. [6], with the -component as the conditioning variable. Appendix § 7 proves both facts (Lemma 7) and makes this connection precise.
The Split and Merge Problems. For a nominal cluster distribution , the split radius is
which is positive when is stable. Similarly, for the nominal pooled distribution of a collection of clusters, the merge radius is
which is positive when is unstable. Both radii equal zero when is critical.
The radii above quantify the robustness of a single cluster to splitting or of a collection of clusters to merging into one. To assess the whole clustering against a set of monitored events, we need a distance on population shifts that accounts for each cluster’s displacement and mass.
Consider a labeled clustering with clusters, indexed by . Let denote the mass of cluster , i.e., its fraction of the population, with , and let denote the nominal and shifted distributions conditional on the cluster label . Write and for the corresponding tuples of cluster distributions. Since labels stay attached to the transported mass, each is preserved, and each cluster moves by its own -structured plan. The population transport cost is the mass-weighted sum of the cluster transport costs. For fixed shifted distributions, the plans can be optimized independently, so the minimum population cost is the mass-weighted sum of the minimum cluster costs. We therefore define the label-preserving -structured transport distance
When finite, it is a conditional 2-Wasserstein distance, conditioned on both the cluster label and the unchanged -component.
Let index the clusters monitored for splitting, and let be the family of collections monitored for merging, with for every . For each such collection, define its mass and nominal pooled distribution by
At temperature , we assume that is stable for every , and is unstable for every . We define the clustering’s robustness certificate as its -distance to the nearest monitored event. This distance is exactly
since the minimum cost of reaching an event is achieved by moving only the clusters involved in it. A structured shift that splits cluster has -distance from of at least , with equality for the shift that moves cluster by a plan attaining its split radius (which exists by Theorem 6) and leaves the other clusters unchanged. Likewise, a structured shift that brings the pooled distribution of to or beyond the merge threshold has -distance of at least , with equality, when this radius is finite, for the shift that moves the clusters in by a plan that attains the merge radius of (which exists by Proposition 4) and leaves the other clusters unchanged. Appendix § 8 gives the formal argument, including the decomposition of this pooled plan into individual cluster plans.
Consequently, every structured shift with avoids all monitored events, and when is finite, some shift at this distance reaches at least one of the events. Computing the robustness certificate therefore reduces to solving the split and merge radius problems (5)–(6), which we investigate next.
Main Results: Split and Merge Radii and SDP Reformulations
The phase-transition analysis of Rose [19] turns the Hessian conditions of DA stability (Definition 1) into conditions on the covariance matrix, which we state in our notation as the following lemma. All proofs for this section are given in Appendix § 9.
Lemma 2 ([19]). Let , , and . Then
with strict positive definiteness of the left-hand side if and only if the inequality on the right-hand side is strict. Hence is stable, critical, or unstable depending on whether is less than, equal to, or greater than , independently of .
Proof. The proof is given in Appendix § 9.§ 1.
We now incorporate the subspace constraint into the displacement coordinates. Let , and let have orthonormal columns spanning . Since columns of form a basis for , every structured displacement is uniquely represented as . We therefore optimize over displacement plans, which are the joint distributions of nominal points and their displacement coordinates
For , let be the distribution of . This construction gives a one-to-one correspondence between any -structured transport plan and its displacement plan , with . The inverse is , and the correspondence preserves cost because . Using Lemma 2, the split and merge problems therefore become
where and . Without loss of generality, we restrict the problems above to displacement plans with zero displacement mean, since otherwise centering the displacements leaves unchanged and strictly reduces the cost.
Let and . For with , define
for the cross-covariance between nominal points and their displacements and the displacement covariance, respectively. Furthermore, define
Proposition 3. The split and merge radii problems are equivalent to
Every feasible pair is realized by the joint law of , where and , where is zero mean and independent of , with covariance . If is optimal, the joint law of is an optimal -structured transport plan.
Proof. The proof is given in Appendix § 9.§ 2.
We next provide SDP formulations of both split (14) and merge (15) problems and characterize their feasibility, attainment, and optimal transport plans.
The Merge Problem. The merge problem (15) is an SDP. The following proposition characterizes its feasibility and shows that, when feasible, a deterministic affine map attains the minimum.
Proposition 4. Let be the orthogonal projection onto . The merge problem (15) is feasible if and only if
Whenever feasible, the minimum is attained by a pair satisfying . The corresponding optimal -structured transport plan is induced by the deterministic affine map .
Proof. The proof is given in Appendix § 9.§ 3.
The Split Problem. The split constraint in (14) is generally nonconvex, so the problem is not directly an SDP. It holds exactly when for some unit vector . Fixing gives an SDP with a closed-form solution for the smallest shift needed to reach the split threshold along . Minimizing this quantity over unit directions yields the split radius and an optimal split direction.
Lemma 5. Let be stable at temperature , so that . For any unit direction , the minimum structured shift needed to reach the split threshold along is
It is feasible exactly when , and the minimum is attained with .
Proof. The proof is given in Appendix § 9.§ 4.
Notice that a unit direction has , which increases the directional cost, but a sufficiently small numerator can compensate and make it optimal (Figure 1). In particular, if , then for every unit , so the cost is minimized along the top eigenvector of , giving . In general, minimizing this cost over unit directions is nonconvex, but the next theorem reformulates it exactly as an SDP.
Theorem 6. Let be stable at temperature . Then the squared split radius is given by the following SDP, which is feasible, and its maximum is always attained:
Proof. The proof is given in Appendix § 9.§ 5, together with the recovery of an attaining split direction and its -structured transport plan.
Numerical Experiments
S1–S3 benchmarks. We use the S1–S3 benchmarks of Fränti and Virmajoki [10]: 5000 points in from 15 Gaussian clusters, with overlap increasing from S1 to S3. Each dataset is centered and normalized to unit root-mean-square norm. We obtain nominal clusterings by running Lloyd’s algorithm initialized at the supplied ground-truth centers; we then hold the labels fixed.
Figure 2 shows the representatives (stars), their Voronoi cells, the covariance ellipses, with semi-axes , and concentric circles of radius . By Lemma 2, a cluster is stable when its ellipse lies strictly inside its circle and reaches the split threshold when the two first touch. For a monitored merge, the analogous threshold is reached when the pooled covariance ellipse first fits inside the circle about its pooled mean; Figure 4 of the appendix illustrates attaining merge shifts.
Figure 2. Nominal clusterings S1–S3 at .
Figure 4. Attaining shifts of the events realizing at (events of Table 1). Each panel shows the nominal (grey) and shifted (black) covariance contours of the affected cluster or pooled pair; the shifted contours touch the circles.
We monitor all 15 splits and the merges of neighboring clusters whose Voronoi cells share an edge. We pick from the common range of temperatures (approximately ) for which every cluster is stable and the pooled distribution of every monitored pair is unstable in all three datasets. Table 1 reports the certificates and attaining events under unrestricted, horizontal, and vertical shifts (, , ); all radii in this section are in units of . The radius SDPs are solved with Clarabel through CVXPY. In S1, merge is the most vulnerable event under unrestricted shifts, with radius 12.08. Its two clusters are aligned nearly vertically, so vertical shifts attain almost the same radius (13.12), whereas under horizontal shifts the most vulnerable event becomes merge , at almost twice the radius (23.38). In S3, split 9 is the most vulnerable event under all three choices of at . To examine the effect of resolution, we keep the S3 clustering and monitored events fixed and consider unrestricted shifts. As increases from 0.10 to 0.12, the minimum mass-weighted split radius rises from 7.23 to 12.59, while the minimum mass-weighted merge radius falls from 15.98 to 7.90. At this coarser resolution, merge therefore replaces split 9 as the most vulnerable event. Appendix E gives event rankings, attaining shifts, and further results for S3 with its clusters moved farther apart.
| Dataset | Event | Event | Event | |||
| S1 | Merge | 12.08 | Merge | 23.38 | Merge | 13.12 |
| S2 | Merge | 12.16 | Merge | 16.69 | Merge | 15.49 |
| S3 | Split 9 | 7.23 | Split 9 | 8.96 | Split 9 | 8.54 |
Table 1. Certificates (units of ) and attaining events at .
Higher-dimensional example: DIM64. To demonstrate the SDP formulations in higher dimensions, we consider the DIM64 benchmark from the same repository: 1024 points in from 16 clusters. We monitor all 16 splits and all 120 pairwise merges. Keeping the nominal clustering and fixed, we enlarge the admissible subspace for , with permitting unrestricted shifts. Since the subspaces are nested, the event radii are nonincreasing in and the number of feasible merges is nondecreasing. Split 13 attains the certificate for every tested , and the certificate decreases from 53.6 to 50.7. No merge is feasible for , and all 120 are feasible at . Table 5 in Appendix § 10 gives the detailed setup and numerical results.
| Weighted split | Weighted merge | Attaining event | Feasible merges | ||
| 10 | 0.053610 | 0.053610 | Split 13 | 0/120 | |
| 30 | 0.052094 | 0.052094 | Split 13 | 0/120 | |
| 50 | 0.051143 | 0.051143 | Split 13 | 0/120 | |
| 55 | 0.050981 | 0.168348 | 0.050981 | Split 13 | 20/120 |
| 60 | 0.050951 | 0.145684 | 0.050951 | Split 13 | 96/120 |
| 64 | 0.050749 | 0.132986 | 0.050749 | Split 13 | 120/120 |
Table 5. DIM64 at : minimum mass-weighted split and merge radii, robustness certificates, and attaining events. All values are distances in normalized coordinates; indicates that no monitored merge is feasible.
Conclusion and discussion
We used the phase-transition analysis of deterministic annealing to formalize split and merge thresholds at a prescribed resolution. We quantified the smallest structured distribution shifts reaching these thresholds, which we call the split and merge radii. We reformulated their computation as exact SDPs, and combined them into an exact robustness certificate for a given labeled clustering. This certificate equals the smallest structured population transport distance to any monitored event. Experiments on two-dimensional and higher-dimensional datasets demonstrated the computational tractability of the formulations and the effect of displacement restrictions on robustness.
The framework can be extended to more general distortions, such as Bregman divergences, and more general transport costs. Another direction is to consider a population evolving under underlying dynamics and design controls to steer its covariance toward desired split or merge thresholds or maintain robustness against unwanted ones, connecting the framework to covariance steering.
DA free energy
Let , and let be a collection of representatives at fixed .
Entropy formulation. Let each point be assigned to representative with probability , where
For representatives , define the expected distortion and conditional assignment entropy by
with . At temperature , the free energy is
For fixed , minimizing over assignments gives the Gibbs probabilities
Substituting these assignments into (19) gives the reduced free energy
as stated in (2).
Zero-temperature limit. Let . Since
taking and integrating gives
Thus, since is fixed, the reduced free energy converges to the distortion uniformly in , as .
Finiteness and attainment of
Lemma 7. For , if and only if and have the same marginal on , in which case the infimum in (4) is attained.
Proof. Let and be the orthogonal projections onto and . For , write and , and define similarly for . Any -structured plan satisfies , equivalently , almost surely. Thus, the -marginals of and must be equal.
Conversely, suppose that and have the same distribution , and let denote the unchanged component. Define
These joint distributions share the marginal on .
This matches the conditional Wasserstein distance formulation of Chemseddine et al. [6], with as the conditioning variable. The orthogonal decomposition preserves cost, since
Thus, is equivalent to their conditional 2-Wasserstein distance between and . Their Proposition 1(iii) constructs an optimal conditional coupling between and , preserving the -component. Let . Then the law of is an optimal -structured plan between and , since almost surely and this correspondence preserves transport costs. Its cost is finite because and .
Proof of the clustering certificate
For a split of cluster , any shift that brings to or beyond the split threshold satisfies , with equality when is transported by a plan attaining its split radius and every other cluster is unchanged.
For a merge, however, it is less obvious that transporting a collection by a pooled structured plan attaining its merge radius incurs -distance , since measures the transport of each cluster separately rather than of the pooled distribution. To show this, suppose the merge radius of is finite, and let be such a plan, i.e., is at or beyond the merge threshold and
We can condition this pooled plan on the cluster label to obtain a -structured transport plan for each cluster , whose first marginal is by construction. Denote the second marginal by , such that
Each is an optimal structured plan between and . Otherwise, some has a lower cost, and replacing by in (23) gives a plan in with a lower cost than , contradicting its optimality. Plugging (23) into (22) therefore gives
Transporting each cluster by and leaving every other cluster unchanged thus reaches the merge event at -distance .
Proofs
Second variation and DA stability
Let , , and . Write , , and . We first derive the second variation at , then use it to prove Lemma 2.
Second variation at coincidence. For a perturbation , with , define
Lemma 8 (Second variation). The configuration is stationary, and the second variation of at is
Proof. Write for the Gibbs assignments at the perturbed configuration. Differentiating (2) with respect to gives
where differentiation under the integral, for both first and second variations, is justified by the finite second moment of .
At , the assignments are uniform, , so
Since this holds for every , .
Differentiating the Gibbs assignments gives
Differentiating (25) once more, using (26), and evaluating at yields
By the definition of , the first two terms equal
which gives (24).
Covariance criterion. We now establish the stability condition from the second variation.
Proof of Lemma 2. The first term of (24) is nonnegative. If , then
The second term is therefore strictly positive for every nonzero . Thus, the Hessian is positive definite, and stationarity implies that is a strict local minimum.
Let be a unit eigenvector corresponding to , and define
Because , the first term of (24) vanishes, giving
If , then , so the Hessian has a negative eigenvalue and is a saddle point. Finally, if , then , so for every . The nonzero perturbation satisfies . Thus, the Hessian is positive semidefinite but singular, and is critical. These three cases establish the claimed equivalences for every .
Proof of Proposition 3
Let and . As discussed in the main text, we assume without loss of generality that . Let and be the associated moment matrices defined in (12). The covariance of the stacked random vector is given by
so . Moreover,
Hence, every centered displacement plan yields a feasible moment pair with the same cost and target covariance.
Conversely, let . The generalized Schur complement gives
Choose and a zero-mean random vector , independent of , with covariance (for example ), and set
The joint law of belongs to , and . Since and are independent and have zero mean, , so
Moreover,
Thus, every feasible moment pair is realized by a centered displacement plan. Finally, if the moment infimum is attained at , the construction above yields an optimal displacement plan . The corresponding optimal -structured transport plan is then given by the joint law of , where .
Proof of Proposition 4
Proof. Since , multiplying the merge constraint by on both sides gives
which proves the necessity of (16). Conversely, suppose this condition holds and choose and . Then
and
Thus, the merge problem is feasible.
We next show that the feasible set is compact. For any feasible pair , multiplying the merge constraint on the left by and on the right by , and using , gives
The block PSD constraint, evaluated on for every , yields
Substituting this bound gives . Rearranging, we obtain
Thus, is bounded. The block PSD constraint also implies that its principal minors are nonnegative, so
Since is fixed and is bounded, every entry of is bounded, and hence is also bounded. The feasible set is also closed and therefore compact, whenever nonempty. Hence, the continuous objective attains its minimum.
Finally, let be an optimal pair. The generalized Schur complement gives
Replacing by still satisfies the block PSD constraint and gives
Thus, the pair is feasible and reduces the objective by . Optimality of implies , and hence .
Consequently, the construction in Proposition 3 gives an optimal displacement
The corresponding optimal -structured transport plan is then given by
Proof of Lemma 5
Proof. Since is stable, for every unit direction . If , then , so for every feasible . Therefore, the directional constraint is infeasible.
Now suppose . By Proposition 3, every is realized by a displacement plan , with and . Expanding the directional constraint gives
Using the definition of and Cauchy–Schwarz, we obtain
It follows that
Moreover, since , one more Cauchy–Schwarz gives
Combining these bounds gives
The bound (29) holds with equality when both (27) and (28) hold with equality. For , this occurs when
if , which gives
If , choose , where is a zero mean and unit variance random variable independent of . This gives
Rearranging (29) under the constraint gives
Choosing in the above feasible pairs so that attains equality in (30). Thus, this lower bound is attained and equals the minimum structured transport cost needed to reach the split threshold along .
Proof of Theorem 6 and recovery of a split direction
Proof. The problem we want to solve is
To put the problem in a form suitable for applying the S-lemma, we reformulate it in the following way
subject to
for all , .
Since is stable, . Taking the square root and rearranging gives
This inequality is automatically satisfied when , so we can include all unit directions. Hence,
We next rewrite the inner maximum using the identity . In particular,
where and are auxiliary vectors. Their choices are independent, so
Consequently, the constraint in (31) is equivalent to
This is equivalent to the quadratic implication
for all . To see this, assume (33) holds. For any and satisfying , apply it to and , then multiply the resulting inequality by . If , then , so the conclusion holds automatically. Conversely, restricting (34) to recovers (33).
For , any and satisfy . Therefore, by the S-lemma, (34) is equivalent to the existence of such that
Expanding , the left-hand side of (35) equals
Its nonnegativity for every is equivalent to
Since (by lower-right block), setting and multiplying (36) by gives
This is now affine in . For positive , every step above is an equivalence.
Note that allowing forces , which already satisfies (31) and therefore does not change the optimal value. Hence, maximizing over subject to (37) gives the SDP in (18).
It is straightforward to check that and , and the feasible set is nonempty, so the maximum is attained.
Recovering an optimal split direction. One way to recover an optimal split direction from is as follows. The constraint (33) can be written as
The maximum is attained by compactness. Since the objective is strictly convex in , an interior point cannot maximize it, so any maximizing pair satisfies . Moreover, the inequality must be tight at optimality. Otherwise, a positive gap would allow every feasible to be scaled by a factor sufficiently close to one while still satisfying the inequality. The larger budget would then be feasible, contradicting optimality. Thus, an attaining pair satisfies
Since , we have . Set , and let denote the matrix in (36) evaluated at . The equalities above make the S-lemma certificate (35) zero, giving
Since , the stacked vector lies in . Hence, recovering reduces to finding
Once such a pair is found, as per (32), the maximization of over is attained at
which recovers a splitting direction . To confirm this, observe that
Both inequalities are therefore equalities, so attains the directional cost . Using this direction in the displacement construction from the proof of Lemma 5 yields an optimal -structured transport plan.
Additional simulations and experiments
S1–S3 SIPU datasets
S3 vs. S3 with clusters moved apart As a controlled check, we scale the S3 cluster means by 1.25, keeping each cluster’s points fixed relative to its mean (Figure 3). As expected, the smallest mass-weighted split radius, attained by split 9, remains unchanged at 7.23, 8.96, and 8.54 under unrestricted, horizontal, and vertical shifts (in units of ). The smallest merge events are also unchanged (4+13, 4+13, and 3+14), but their mass-weighted radii increase from 16.0, 16.8, and 19.0 to 36.8, 39.4, and 39.7, roughly by a factor of 2.1–2.3, so, as expected, the clustering becomes more robust to merges.

Figure 3. (a) S3 and (b) S3 with cluster means scaled by 1.25, at and on the same axes. The covariance ellipses and circles are unchanged.
Minimum split and merge radii Tables 2 and 3 report the minimum unweighted and mass-weighted split and merge radii. Mass weighting can change which event is most vulnerable: under unrestricted shifts in S1, cluster 10 has the smallest split radius, but splitting cluster 1 requires the least population transport distance. Figure 4 shows attaining shifts for the certificate-attaining events.
| Dataset | Weighting | Unrestricted Event | Unrestricted Radius | Horizontal Event | Horizontal Radius | Vertical Event | Vertical Radius |
| S1 | Unweighted | Split 10 | 115.56 | Split 10 | 115.92 | Split 10 | 122.59 |
| S1 | Mass-weighted | Split 1 | 29.44 | Split 1 | 29.60 | Split 10 | 31.97 |
| S2 | Unweighted | Split 14 | 75.42 | Split 14 | 79.78 | Split 14 | 86.40 |
| S2 | Mass-weighted | Split 14 | 19.52 | Split 14 | 20.65 | Split 14 | 22.36 |
| S3 | Unweighted | Split 9 | 28.80 | Split 9 | 35.68 | Split 9 | 34.02 |
| S3 | Mass-weighted | Split 9 | 7.23 | Split 9 | 8.96 | Split 9 | 8.54 |
Table 2. Minimum split radii at . Unweighted rows minimize over clusters ; mass-weighted rows minimize . All values are reported in units of . Bold values attain the clustering certificate .
For unrestricted shifts across S1–S3, Table 4 reports the three smallest split and merge radii, ranked separately before and after mass weighting, with ratios to their respective minima.
| Dataset | Weighting | Rank | Splits Event | Splits Radius | Splits Ratio | Merges Event | Merges Radius | Merges Ratio |
| S1 | Unweighted | 1 | Split 10 | 115.56 | 1.0000 | Merge | 32.78 | 1.0000 |
| S1 | Unweighted | 2 | Split 11 | 115.59 | 1.0002 | Merge | 39.13 | 1.1939 |
| S1 | Unweighted | 3 | Split 1 | 120.79 | 1.0453 | Merge | 48.91 | 1.4921 |
| S1 | Mass-weighted | 1 | Split 1 | 29.44 | 1.0000 | Merge | 12.08 | 1.0000 |
| S1 | Mass-weighted | 2 | Split 10 | 30.14 | 1.0236 | Merge | 14.03 | 1.1618 |
| S1 | Mass-weighted | 3 | Split 11 | 30.41 | 1.0328 | Merge | 17.39 | 1.4396 |
| S2 | Unweighted | 1 | Split 14 | 75.42 | 1.0000 | Merge | 33.36 | 1.0000 |
| S2 | Unweighted | 2 | Split 12 | 86.12 | 1.1419 | Merge | 42.29 | 1.2677 |
| S2 | Unweighted | 3 | Split 5 | 91.22 | 1.2096 | Merge | 43.17 | 1.2943 |
| S2 | Mass-weighted | 1 | Split 14 | 19.52 | 1.0000 | Merge | 12.16 | 1.0000 |
| S2 | Mass-weighted | 2 | Split 12 | 22.49 | 1.1521 | Merge | 15.12 | 1.2427 |
| S2 | Mass-weighted | 3 | Split 5 | 23.51 | 1.2042 | Merge | 15.86 | 1.3040 |
| S3 | Unweighted | 1 | Split 9 | 28.80 | 1.0000 | Merge | 42.20 | 1.0000 |
| S3 | Unweighted | 2 | Split 5 | 38.87 | 1.3493 | Merge | 50.54 | 1.1977 |
| S3 | Unweighted | 3 | Split 12 | 45.58 | 1.5825 | Merge | 53.78 | 1.2746 |
| S3 | Mass-weighted | 1 | Split 9 | 7.23 | 1.0000 | Merge | 15.98 | 1.0000 |
| S3 | Mass-weighted | 2 | Split 5 | 9.39 | 1.2992 | Merge | 18.37 | 1.1499 |
| S3 | Mass-weighted | 3 | Split 12 | 11.69 | 1.6173 | Merge | 19.89 | 1.2449 |
Table 4. Three smallest split and merge radii under unrestricted shifts at . Rankings are computed separately for each dataset, event type, and weighting. Radii are reported in units of ; mass-weighted radii are population transport distances . Each ratio is relative to the minimum in its own ranking. Merge rankings include only monitored neighboring pairs. Event labels match Figure 2.
| Dataset | Weighting | Unrestricted Event | Unrestricted Radius | Horizontal Event | Horizontal Radius | Vertical Event | Vertical Radius |
| S1 | Unweighted | Merge | 32.78 | Merge | 64.61 | Merge | 35.60 |
| S1 | Mass-weighted | Merge | 12.08 | Merge | 23.38 | Merge | 13.12 |
| S1 | Feasible pairs | 34/34 | 13/34 | 14/34 | |||
| S2 | Unweighted | Merge | 33.36 | Merge | 45.76 | Merge | 43.34 |
| S2 | Mass-weighted | Merge | 12.16 | Merge | 16.69 | Merge | 15.49 |
| S2 | Feasible pairs | 33/33 | 14/33 | 14/33 | |||
| S3 | Unweighted | Merge | 42.20 | Merge | 44.44 | Merge | 52.12 |
| S3 | Mass-weighted | Merge | 15.98 | Merge | 16.83 | Merge | 18.95 |
| S3 | Feasible pairs | 35/35 | 14/35 | 14/35 |
Table 3. Minimum merge radii at . Unweighted rows minimize over monitored pairs ; mass-weighted rows minimize . All radii are reported in units of . Bold values attain the clustering certificate . Feasible-pair counts give the number of finite merge radii out of all monitored pairs.
Higher-dimensional example: DIM64
We consider the DIM64 benchmark from the same SIPU repository, with 1024 points in and 16 clusters. Centering, normalization, and the Lloyd initialization are the same as for S1–S3. The resulting labels are held fixed, and we use the same temperature . Feasible radius problems are solved using SCS through CVXPY. If a merge fails the feasibility condition (16), no SDP solve is required.
References
- [1]Daniel Aloise, Amit Deshpande, Pierre Hansen, and Preyas Popat. NP-hardness of Euclidean sum-of-squares clustering. Machine Learning, 75(2):245–248, May 2009. ISSN 1573-0565. doi: 10.1007/s10994-009-5103-0. URL https://doi.org/10.1007/s10994-009-5103-0.
- [2]Pranjal Awasthi, Avrim Blum, and Or Sheffet. Center-based clustering under perturbation stability. Information Processing Letters, 112(1):49–54, January 2012. ISSN 0020-0190. doi: 10.1016/j.ipl.2011.10.006. URL https://www.sciencedirect.com/science/article/pii/S0020019011002778.DOI
- [3]Isin M. Balci and Efstathios Bakolas. Exact SDP Formulation for Discrete-Time Covariance Steering with Wasserstein Terminal Cost, May 2022. URL http://arxiv.org/abs/2205.10740. arXiv:2205.10740 [math.OC].
- [5]Shai Ben-David, Ulrike von Luxburg, and Dávid Pál. A Sober Look at Clustering Stability. In Gábor Lugosi and Hans Ulrich Simon, editors, Learning Theory, pages 5–19, Berlin, Heidelberg, 2006. Springer. ISBN 978-3-540-35296-9. doi: 10.1007/11776420_4.
- [6]Jannis Chemseddine, Paul Hagemann, Gabriele Steidl, and Christian Wald. Conditional Wasserstein Distances with Applications in Bayesian OT Flow Matching. Journal of Machine Learning Research, 26 (141):1–47, 2025. ISSN 1533-7928. URL http://jmlr.org/papers/v26/24-0586.html.arxiv.org/abs/2403.18705
- [7]Yongxin Chen, Tryphon T. Georgiou, and Michele Pavon. Optimal Steering of a Linear Stochastic System to a Final Probability Distribution, Part I. IEEE Transactions on Automatic Control, 61(5):1158–1169, May 2016. ISSN 1558-2523. doi: 10.1109/TAC.2015.2457784. URL https://ieeexplore.ieee.org/document/7160692.DOI
- [9]Hamza Fawzi, Paulo Tabuada, and Suhas Diggavi. Secure Estimation and Control for Cyber-Physical Systems Under Adversarial Attacks. IEEE Transactions on Automatic Control, 59(6):1454–1467, June 2014. ISSN 1558-2523. doi: 10.1109/TAC.2014.2303233. URL https://ieeexplore.ieee.org/document/6727407.DOI
- [10]Pasi Fränti and Olli Virmajoki. Iterative shrinking method for clustering problems. Pattern Recognition, 39(5):761–775, May 2006. ISSN 0031-3203. doi: 10.1016/j.patcog.2005.09.012. URL https://www.sciencedirect.com/science/article/pii/S0031320305003778.DOI
- [11]Rui Gao and Anton Kleywegt. Distributionally Robust Stochastic Optimization with Wasserstein Distance. Mathematics of Operations Research, 48(2):603–655, May 2023. ISSN 0364-765X. doi: 10.1287/moor.2022.1275. URL https://pubsonline.informs.org/doi/full/10.1287/moor.2022.1275.DOI
- [12]Chuan Guo, Jared S. Frank, and Kilian Q. Weinberger. Low Frequency Adversarial Perturbation. In Proceedings of The 35th Uncertainty in Artificial Intelligence Conference, pages 1127–1137. PMLR, August 2020. URL https://proceedings.mlr.press/v115/guo20a.html.
- [13]Vikrant Malik, Taylan Kargin, and Babak Hassibi. Distributionally Robust K-Means Clustering, 2026. URL https://arxiv.org/abs/2604.11118. Version Number: 1.
- [15]Christos N. Mavridis and John S. Baras. Annealing Optimization for Progressive Learning With Stochastic Approximation. IEEE Transactions on Automatic Control, 68(5):2862–2874, May 2023b. ISSN 1558-2523. doi: 10.1109/TAC.2022.3232706. URL https://ieeexplore.ieee.org/document/10002308.DOI
- [16]Robert J. McCann and Brendan Pass. Optimal Transportation Between Unequal Dimensions. Archive for Rational Mechanics and Analysis, 238(3):1475–1520, December 2020. ISSN 1432-0673. doi: 10.1007/s00205-020-01569-5. URL https://doi.org/10.1007/s00205-020-01569-5.
- [17]Peyman Mohajerin Esfahani and Daniel Kuhn. Data-driven distributionally robust optimization using the Wasserstein metric: performance guarantees and tractable reformulations. Mathematical Programming, 171(1):115–166, September 2018. ISSN 1436-4646. doi: 10.1007/s10107-017-1172-1. URL https://doi.org/10.1007/s10107-017-1172-1.
- [18]Gabriel Peyré and Marco Cuturi. Computational Optimal Transport with Applications to Data Sciences. Foundations and Trends in Machine Learning, 11(5-6):355–607, February 2019. ISSN 1935-8237. doi: 10.1561/2200000073. URL https://doi.org/10.1561/2200000073.
- [19]K. Rose. Deterministic annealing for clustering, compression, classification, regression, and related optimization problems. Proceedings of the IEEE, 86(11):2210–2239, November 1998. ISSN 1558-2256. doi: 10.1109/5.726788. URL https://ieeexplore.ieee.org/document/726788/.DOI
- [21]Amber Srivastava, Mayank Baranwal, and Srinivasa Salapaka. On the Persistence of Clustering Solutions and True Number of Clusters in a Dataset. Proceedings of the AAAI Conference on Artificial Intelligence, 33(01):5000–5007, July 2019. ISSN 2374-3468. doi: 10.1609/aaai.v33i01.33015000. URL https://ojs.aaai.org/index.php/AAAI/article/view/4431.DOI
- [22]Berk Ustun, Alexander Spangher, and Yang Liu. Actionable Recourse in Linear Classification. In Proceedings of the Conference on Fairness, Accountability, and Transparency, FAT* ’19, pages 10–19, New York, NY, USA, January 2019. Association for Computing Machinery. ISBN 978-1-4503-6125-5. doi: 10.1145/3287560.3287566. URL https://dl.acm.org/doi/10.1145/3287560.3287566.DOI


