Psychiatric and critical-care researchers often cluster patients into "subtypes" and then report that a treatment works for one of them. These subtypes frequently fail to replicate. Two explanations are usually blurred together. The clustering algorithm may have stopped at a poor local solution, which is an optimization failure. Or the data may support many very different groupings that fit almost equally well, which is an identifiability failure. Restarts and bootstrap resampling cannot cleanly separate the two. Exact global optimization can. Branch-and-bound methods search the space of cluster centers while maintaining a proven lower bound on how good any solution can be. We propose using such a solver not only to find the best partition but to certify a fragility number: the largest fraction of patient pairs that any partition fitting within ε of the optimum can regroup differently from the reported one. A small certified fragility means the subtype claim is robust to optimization. A large one means the data do not determine the subtypes, whatever the algorithm.
The second half of the proposal treats the qualitative record as an independent witness, following mixed-methods practice. Clinical notes and narrative reports are kept out of the clustering objective and used afterward to arbitrate. When several very different near-optimal partitions exist, we ask whether the narrative stream distinguishes them. We also ask whether the patients who change groups across near-optimal partitions are the ones whose notes describe mixed or atypical presentations. This turns triangulation, the mixed-methods practice of checking one data stream against another independent one, into a quantitative test. The test is applied to a certified object rather than to an artifact of a random seed.
Core Claim
For low- to moderate-dimensional clinical feature spaces, a center-branching global solver for sum-of-squares clustering can be extended to return three things: a certified optimum, a certified upper bound on partition fragility at tolerance ε, and explicit witness partitions that attain high fragility. Let $f(P)$ be the within-cluster sum of squares of partition $P$, and let $U$ and $L$ be the solver's certified upper and lower bounds on the optimum. Let $\hat P$ be the reported partition. Define
$$D_\varepsilon = \max_{P:\, f(P) \le (1+\varepsilon)U} \; d(P,\hat P),$$
where $d$ is the fraction of patient pairs that are grouped together in one partition and apart in the other. Using pairs rather than labels makes $d$ unaffected by how the subtypes are numbered. The claim has two parts. First, $D_\varepsilon$ can be bounded from above inside the same branch-and-bound tree, because fixing a box of candidate centers fixes the assignment of every patient whose nearest center does not change within that box. Second, on real clinical cohorts, this certified number will sometimes disagree sharply with what restart-based stability analysis suggests. Where it does, narrative evidence can tell us which near-optimal partition is clinically meaningful, or whether none is.
Relation to Prior Work
The method builds directly on A Scalable Deterministic Global Optimization Algorithm for Clustering Problems. That work solves minimum sum-of-squares clustering to a certified gap by branching only on cluster centers and computing lower bounds by Lagrangian decomposition. It reaches a 0.1% gap on Iris, Seeds and Glass in about an hour on 20 cores, while CPLEX found no feasible solution within 4 hours on a 42,000-sample instance. It certifies a single optimal value. It does not ask how different the other near-optimal partitions are, and it never touches clinical data. Our contribution is the fragility bound, which reuses its center-branching tree.
Two other relaxation-based clusterers take a different route. Certifying Global Optimality of Graph Cuts via Semidefinite Relaxation proves exact recovery under spectral separation conditions, but only on synthetic shapes. Subspace Clustering with Priors via Sparse QCQP shows that domain priors such as must-link pairs and outlier budgets can enter a tight relaxation. It reports 4.29% misclassification on Merton I against near 50% for GPCA. We borrow its idea of constraining the feasible set only for the nuisance-invariance analysis described below. We deliberately do not inject narrative-derived constraints into the objective, because doing so would destroy the independence of the qualitative witness.
The motivation comes from the clinical heterogeneity literature. Mode-Aware Phenotype Profiling from Korean Clinical Reports clustered LLM-extracted autism phenotype proportions, after isometric log-ratio (ILR) transformation, with Gaussian mixtures. The resulting modes explained only 24.7% of phenotypic variance, and one mode was driven by report format rather than by the patients. This is exactly the weak-structure regime where fragility should be large. Patterns of schizophrenia symptoms found three groups with k-means on PANSS items in 218 patients. It also found that linear models matched nonlinear ones, which constrains us toward simple Euclidean objectives rather than deep embeddings. A Pipeline for Interpretable Clinical Subtyping with Deep Metric Learning reports three shock subtypes in MIMIC-III, and TACCO reports deep hypergraph co-clustering of EHR data. Both end in heuristic clustering steps whose stability is never certified. Peripheral inflammatory biomarkers define biotypes of bipolar depression shows why this matters: a treatment effect in one biotype out of three, with n = 60, is precisely the kind of claim whose partition should be checked for fragility.
The mixed-methods side supplies the evaluation logic. Two studies used independent qualitative streams to expose things the structured instruments hid. In Why parents consent to their children's participation in genetic research, interviews revealed that 83% of parents expected direct clinical benefit despite formally valid consent. In "How is your thesis going?", open-text coding identified structural stressors behind the psychometric scores. Neither study couples that logic to any clustering algorithm.
Research Program
The first component is algorithmic. Within the center-branching tree, each box of candidate centers whose objective lower bound exceeds $(1+\varepsilon)U$ is pruned. In each surviving box, every patient falls into one of two cases. Either the patient's nearest center is invariant across the box, so its assignment is fixed, or the patient is ambiguous among a known subset of clusters. An upper bound on $d(P,\hat P)$ over the box follows by counting the pairs that are either fixed-and-disagreeing or involve at least one ambiguous patient. Branching then refines boxes until either the global bound on $D_\varepsilon$ meets the best witness found or a time budget expires. Witnesses are produced by local search seeded from surviving boxes.
The bound is loose when many patients are ambiguous. Its tightness is therefore an empirical question we will report rather than assume, as the gap between the certified bound and the best witness. We will run each $k$ from 2 to 6 separately, since the solver requires $k$ fixed in advance, and report fragility as a curve over $k$ and over ε ∈ {0.5%, 1%, 2%, 5%}.
The second component is nuisance invariance. We add a balance constraint requiring each cluster's mix of documentation type or recording site to match the cohort mix. The certified increase in optimal objective under that constraint is the "price of invariance." A large price indicates that the unconstrained optimum is partly organized around the nuisance variable, which turns the M4 observation from the Korean reports study into a measurable quantity.
The third component is the qualitative witness. For each cohort we build a narrative feature stream from free text that was not used in clustering. For MIMIC-III this means discharge summaries. For the autism and schizophrenia cohorts, available only through data-sharing agreements, it means the clinical report text or interview notes. Features are extracted by an LLM and validated against a small expert-annotated subset, following the silver-versus-gold protocol of the Korean reports study, which reported correlations of at least 0.93.
We then test two hypotheses. The first is that, among near-optimal partitions, narrative features separate some partitions markedly better than others; we measure this with held-out classification of cluster labels from narrative features. The second is that patients who switch groups across the near-optimal set have notes coded as mixed, transitional or atypical more often than patients with stable assignments. To keep the coding blind to the quantitative result, a clinician panel will review exemplar patients from competing witness partitions. That review is the qualitative strand proper.
Baselines
The naive reference point is what most subtyping papers report: a single k-means or Gaussian-mixture fit, with the number of clusters chosen by an information criterion. Its implied fragility is zero, because only one partition is ever considered. Any certified $D_\varepsilon$ substantially above zero on a published cohort is evidence that this reporting practice overstates certainty.
The strongest practical competitor is restart-and-resample stability analysis. We run k-means from many random starts plus bootstrap consensus clustering, then estimate fragility as the maximum pairwise disagreement with $\hat P$ among all restart solutions whose objective falls within $(1+\varepsilon)U$. For fairness it receives the same wall-clock and core budget as the certified solver. On the benchmarks in the file that budget is roughly an hour on 20 cores, enough for millions of restarts on cohorts of a few hundred patients.
The certified method beats it if, on at least one real clinical cohort, it finds witness partitions whose disagreement exceeds the restart estimate by a margin we will pre-register: five percentage points of patient pairs. Alternatively, it beats it if it proves an upper bound that rules out fragility levels the bootstrap analysis wrongly suggests. If restarts match the certified bound everywhere, we will report that the certificate adds assurance but not new findings.
The strongest existing global method is the solver of A Scalable Deterministic Global Optimization Algorithm for Clustering Problems, run unmodified. Its reported figure is a 0.1% certified gap on Iris, Seeds and Glass in about an hour on 20 cores. We first reproduce that figure as a sanity check, then measure the overhead our fragility bounding adds at the same gap.
The deep subtyping pipelines, deep metric learning followed by k-means as in A Pipeline for Interpretable Clinical Subtyping, are rerun on the MIMIC-III shock cohort with many seeds. Their seed-to-seed disagreement is compared against certified fragility in the raw feature space. No reported stability or replication number for these pipelines was found on Lacuna, so this comparison is new measurement rather than a comparison with a published figure.
The key ablation removes certification while keeping everything else, the witness search, the narrative arbitration and the invariance constraint. This isolates whether the certificate itself changes any conclusion.
Why not just…?
Why not just run k-means thousands of times and bootstrap? This is the real threat. On small, low-dimensional cohorts, massive restarts may find every near-optimal partition. The global-solver literature shows k-means stalls in poor optima on Glass, but that concerns the optimal value, not the diversity of near-optimal partitions, so it does not settle our question. Restarts can only show that alternatives exist. They cannot prove that none beyond those found exist, and bootstrap mixes sampling noise with optimization noise. The restart baseline under matched budget is designed to answer whether this matters in practice. We commit to reporting a null if restarts are always tight.
Why not just choose $k$ with BIC or the gap statistic and declare the structure real or not? Those criteria score how well a model fits. They do not say whether the reported partition is the only good one. A cohort can favor $k = 3$ strongly while two quite different three-way splits fit equally well. The Korean reports finding, that hard modes explain only 24.7% of variance, is exactly the case where model-selection criteria can pick a $k$ while the partition stays undetermined. We will report BIC alongside fragility to show where they diverge.
Why not just put narrative-derived must-link constraints into the clustering, as the QCQP prior work allows? That would sharpen the partition, but it would use the qualitative stream to create the agreement we then measure, which defeats triangulation. A reviewer could reasonably argue that constraining is more useful clinically. We therefore run the constrained variant as a secondary analysis, using must-links extracted from notes, and report how much objective cost those constraints incur. A cheap constraint set that falls inside the near-optimal set is itself evidence that the narratives pick out one of the competing partitions.
Why not just use deep embedded clustering, which reports better separation? TACCO's 77.93% silhouette improvement measures compactness in a learned space, not replicability. Moreover, the PANSS study found linear models matched nonlinear ones on psychiatric items. The multi-seed comparison above tests whether deep pipelines reduce or merely hide fragility.
Proposed Experiments
Sanity checks come first. On Iris, Seeds and Glass, and on synthetic mixtures with a planted ambiguous region, we verify that the certified fragility bound contains the planted alternative partitions and measure the gap between bound and witness.
The main clinical testbed is the MIMIC-III shock cohort, built from hourly-binned labs and vitals summarized per stay as in the deep metric learning pipeline. It is publicly available and has accompanying notes. Secondary cohorts, subject to data access, are the 30-item PANSS data, with its three reported groups to be checked for fragility, and the ILR-transformed 18-domain autism profiles, where report type serves as the nuisance variable for the invariance experiment. For the 60-patient bipolar cytokine cohort, if obtainable, we will ask whether the treatment-responsive biotype survives as a stable group across the near-optimal set. Scaling remains the main technical risk. The prior solver's reach of 210,000 samples is encouraging, but our bound is looser than a value certificate, and the 17-dimensional ILR space may be hard.
Three outcomes would be decisive. The first is whether certified fragility for any published clinical partition is large at ε = 1%, and whether restarts under an equal budget miss it. The second is whether the price of invariance on the autism data confirms that the format-driven mode is optimization-favored rather than accidental. The third is whether patients who switch groups across near-optimal partitions are over-represented among those whose notes the blinded clinician panel codes as mixed presentations. A positive answer to the third would give the first quantitative link between a certified property of an optimization problem and a qualitative clinical judgment.
References
- A Scalable Deterministic Global Optimization Algorithm for Clustering Problems
- Certifying Global Optimality of Graph Cuts via Semidefinite Relaxation: A Performance Guarantee for Spectral Clustering
- Subspace Clustering with Priors via Sparse Quadratically Constrained Quadratic Programming
- Mode-Aware Phenotype Profiling from Korean Clinical Reports: An LLM-Derived Two-Layer Fingerprint for Autism Characterization
- Patterns of schizophrenia symptoms: hidden structure in the PANSS questionnaire
- A Pipeline for Interpretable Clinical Subtyping with Deep Metric Learning
- TACCO: Task-guided Co-clustering of Clinical Concepts and Patient Visits for Disease Subtyping based on EHR Data
- Peripheral inflammatory biomarkers define biotypes of bipolar depression
- Why parents consent to their children’s participation in genetic research: A study of parental decision making
- “How is your thesis going?”–Ph.D. students’ perspectives on mental health and stress in academia