Metric repair is two problems: Which edges, and what weights

Abstract

Real distance data rarely cooperate: measurements are noisy, observations are missing, and the numbers that result seldom satisfy the triangle inequality. A family of methods exists to correct them, and every one of those methods rests on the same hope --- that analysis run on the corrected data is a more faithful surrogate for the truth than analysis run on the raw data. We are not aware of anyone having tested that hope. We test it through the problem of Metric Repair, which asks for the fewest edges whose reweighting restores the triangle inequality. We implement a suite of algorithms, covering the literature and new methods, both with theoretical guarantees and heuristics, and evaluate their performance on real and synthetic data, both inherently non metric and corrupted. We demonstrate that the algorithms'performance is determined predominantly by the type and fraction of corruption, rather than the corruption's magnitude or graph size. We further test the effect of repair on downstream tasks, namely MDS and $k$NN, and ask if the repair got the result closer to the truth compared to a corrupted instance. In most cases it did not, and we identify the culprit. A small set of edges is not enough. Finding the correct set of edges, be it an injected corruption or a natural non-metricity, is critical. Moreover, deciding on a weight rule impacts performance: on data instances with available metric ground truth, a metric repair algorithm can pull the graph further from the truth, while an oracle access to the true weights helps. Surprisingly, the opposite can be true as well. Setting the weights is not an implementation detail; it is half the problem.