Many learning pipelines start from a table of pairwise distances: nearest-neighbor classifiers, clustering, graph embeddings. When those distances are noisy or incomplete they often break the triangle inequality, the rule that going directly from $i$ to $j$ is never longer than going through a third point $k$. "Metric repair" methods find the closest table of distances that obeys this rule. There is one such inequality for every triple of points, so their number grows with the cube of the dataset size, and most research in this area is about getting past that cost. That line of work has made real progress. Solvers now scale from a few hundred points to ten thousand or more. Yet almost every reported result comes from one kind of test: a distance matrix corrupted by independent Gaussian noise or by uniformly random deletions, scored by how close the repaired matrix is to the input and by the fraction of triangles it satisfies.
This proposal treats that test as a case of synthetic-data reliance and asks whether the conclusions carry over to corruption that looks like real measurement failure. Real failures tend to be concentrated on a few bad points, one-sided, missing in a systematic pattern, or produced by degraded features. We will also ask whether a repaired matrix can stand in for the clean one in downstream tasks. The expected result is a rank-reversal finding: the method that looks best under i.i.d. noise is not the one that best preserves downstream utility under structured corruption. We also expect a satisfied-triangle ratio of 100% to predict very little about usefulness.
Core Claim
The metric-repair literature measures success in a narrow way. The Metric Nearness Problem, which introduced triangle-fixing algorithms, benchmarks only on synthetic random matrices of size 25 to 225. Metric Nearness Made Practical scales to $n=10{,}000$ with a two-stage method: a warm start that projects onto Euclidean-embeddable distances, then alternating projections onto the triangle constraints, a scheme known as HLWB. It reports constraint satisfaction ratio (CSR) and normalized mean squared error (NMSE) on synthetic graphs and MNIST. MetricEmbedding builds distances from "tropical" inner products, $\max_i(u_i+v_i)$, which satisfy the triangle inequality by construction. It tests on Cora and on synthetic matrices with Gaussian noise and 30–50% random missingness.
Two findings from synthetic-data evaluation make this narrowness worrying. TabStruct shows that data can score well on local metrics while destroying global structure. On the Equivalency, Substitutability, and Flexibility of Synthetic Data shows that what matters is whether data can replace real data in a downstream task, and that simple synthetic data can even hurt performance. We import both lessons.
The specific, testable claim has three parts. First, under structured corruption, method rankings by NMSE and downstream utility diverge from rankings under i.i.d. noise. Second, corruption concentrated on a few points favors sparse, localized repair, meaning ℓ1-style methods and sparse metric repair, over ℓ2 methods such as HLWB and the fixed-dimension tropical model, because ℓ2 methods spread one bad point's error across the whole matrix. Third, for a nontrivial fraction of settings, the unrepaired matrix is as useful downstream as any repaired one.
Research Program
We will build a corruption suite with ground truth. We start from clean distance matrices on MNIST, Cora, and the synthetic Graph-t1/Graph-t2 graphs from Metric Nearness Made Practical. We then apply two reference corruptions used in prior work, i.i.d. Gaussian noise and uniform masking, and four structured families that model plausible real failures. The first is point-localized corruption, where a small set of points has all its distances perturbed, as a failing sensor or mislabeled item would produce. The second is feature-induced corruption: distances are recomputed from degraded inputs (blurred or occluded MNIST images, Cora bag-of-words vectors with words dropped), so the errors are correlated in the way real pipeline errors are. The third is one-sided under-reporting. The fourth is missing-not-at-random masking, where large distances are mostly absent, as in sparse k-nearest-neighbor graphs.
Every family will be matched to the reference corruptions at equal NMSE and at equal count of violated triangles. Without this matching, any difference we find could simply mean the structured corruption is more severe. Unrolling Swiss Cheese and Unsupervised Metric Learning in Presence of Missing Data report recovery with up to half of the distances missing. They motivate the missing-data axis, and we test whether that recovery holds when the missingness is not random.
We will score every repaired matrix three ways. The first is fidelity to the clean matrix, as opposed to the corrupted input that prior work compares against. The second is CSR. The third is downstream substitutability: k-nearest-neighbor accuracy and neighbor recall against clean labels and clean neighborhoods, and spectral-clustering adjusted Rand index. Following the equivalency paper, we will also report the largest fraction of clean distances that can be replaced by repaired ones before downstream performance drops. The analysis centers on Kendall rank correlation between method orderings under the reference and structured corruptions, and on how well CSR and NMSE predict downstream utility.
Baselines
The naive reference point is to do nothing: feed the corrupted matrix, with missing entries filled by the row median, directly to each downstream task. If repair cannot beat this, the cubic-constraint effort has no practical payoff in that regime. We will report this outcome honestly.
The strongest scalable competitors are HLWB from Metric Nearness Made Practical, which reports CSR reaching 1.0 and convergence in about 50 seconds on MNIST at $n=1{,}500$, roughly 34 times faster than earlier triangle fixing and Project-and-Forget, and MetricEmbedding, which reports exactly 0% violations and about 26 seconds on Cora at $n=1{,}000$, where HLWB and triangle fixing did not converge within 2,000 seconds. No reported result found on Lacuna for the downstream task utility of either method's repaired matrices, so the downstream numbers will be new.
We also run ℓ1 and ℓ2 triangle fixing and decrease-only repair, which is equivalent to all-pairs shortest paths, from The Metric Nearness Problem, together with sparse metric repair. An ablation runs HLWB's Euclidean warm start alone, without the polishing stage. This isolates whether enforcing general triangle constraints adds anything beyond Euclidean projection.
For fairness, all methods receive identical corrupted matrices at $n \in \{1{,}000, 2{,}000\}$, where every method runs. Only the scalable methods are run at $n=10{,}000$. Each method gets the same wall-clock budget and the same hyperparameter search budget, covering MetricEmbedding's latent dimension $k$, the ℓ1 smoothing parameter, and iteration counts. Hyperparameters are tuned on a held-out corruption seed. One tuning track uses clean-matrix fidelity and a second uses only input-side criteria, since practitioners do not have the clean matrix.
A method "wins" a structured family if its downstream score beats both do-nothing and the best reference-noise winner by more than the seed-to-seed standard deviation across five seeds.
Why not just…?
Why not just take shortest paths, which are automatically metric? Shortest paths can only shrink distances. The Metric Nearness Problem shows this is exactly decrease-only repair, so it should bias results under one-sided under-reporting and missing large distances. It may work well under over-reporting corruption. We include it as a full baseline rather than assume it loses, and our per-family results will show where it is sufficient.
Why not just project onto Euclidean distances and stop? Metric Nearness Made Practical argues that Euclidean-embeddable metrics are a strict subset of all metrics, so this projection distorts Cosine, Manhattan, or graph distances. Its evidence concerns fidelity, not downstream use, and for k-nearest-neighbor tasks a rough Euclidean projection may be enough. The warm-start-only ablation settles the question. If it matches full HLWB downstream, that itself is a finding against the need for cubic constraint enforcement.
Why not just test with heavier-tailed or larger i.i.d. noise? Matching severity is exactly what our controls do. If rankings under structured corruption agree with rankings under i.i.d. noise at matched NMSE and matched violation count, the core claim fails, and the conclusion would be that existing synthetic benchmarks are adequate. That result is also worth publishing.
Why not just trust CSR, since a valid metric is what downstream methods need? TabStruct and the relational fidelity benchmark both find that validity or fidelity scores correlate only moderately with utility. We test the analogous claim directly by correlating CSR with downstream accuracy across all runs.
Proposed Experiments
The first decisive check is rank transfer. We compute Kendall's τ between method orderings on downstream accuracy under i.i.d. Gaussian noise versus each structured family, at matched severity. A τ below about 0.4 on at least two families supports the claim, and a τ near 1 refutes it.
The second check is locality. Under point-localized corruption, we test whether ℓ1 triangle fixing and sparse repair beat HLWB and MetricEmbedding on neighbor recall of the uncorrupted points. The mechanism predicts that ℓ2 methods damage clean points' neighborhoods to accommodate the corrupted ones.
The third check covers non-random missingness. With large distances missing, we test whether MetricEmbedding's reported robustness to 30–50% uniform missingness holds, and how its accuracy varies with $k$.
The fourth check is substitutability. For each method and family, we report the replacement fraction at which k-nearest-neighbor accuracy falls one standard deviation below the clean-matrix result, and we count the settings where do-nothing is statistically tied with the best repair.
All code and corruption generators will be released so that future metric-repair papers can report results under structured corruption alongside the existing i.i.d. tests.
References
- The Metric Nearness Problem
- Metric Nearness Made Practical
- MetricEmbedding: Accelerate Metric Nearness by Tropical Inner Product
- TabStruct: Measuring Structural Fidelity of Tabular Data
- On the Equivalency, Substitutability, and Flexibility of Synthetic Data
- If it ain't broke, don't fix it: Sparse metric repair
- Unrolling Swiss Cheese: Metric repair on manifolds with holes.
- Unsupervised Metric Learning in Presence of Missing Data
- Benchmarking the Fidelity and Utility of Synthetic Relational Data