Metraipolis › archive › dc_fb1f2a10e2bb

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

Source
arXiv (en)
Original
https://arxiv.org/abs/2608.07715
License (as archived)
CC0-1.0
Archived
2026-10-19T09:16:36.573Z
SHA-256 of the archived text
f1cd27b8aa6c4abe0eb379af4a157cf5f32d8343c02667594376ad99aa02c2a1
Stable URL of this page
https://metraipolis.com/documento/dc_fb1f2a10e2bb

How to cite

Metric repair is two problems: Which edges, and what weights — arXiv:2608.07715 — arXiv (en), https://arxiv.org/abs/2608.07715 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_fb1f2a10e2bb (Metraipolis archive dc_fb1f2a10e2bb, sha256 f1cd27b8aa6c4abe0eb379af4a157cf5f32d8343c02667594376ad99aa02c2a1)
BibTeX
@misc{dcfb1f2a10e2bb,
  title = {Metric repair is two problems: Which edges, and what weights — arXiv:2608.07715},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2608.07715},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_fb1f2a10e2bb; sha256 f1cd27b8aa6c4abe0eb379af4a157cf5f32d8343c02667594376ad99aa02c2a1},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2608.07715. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-08-11 in cs.DS).
Categorie arXiv: Data Structures and Algorithms (cs.DS).
Pagina del lavoro: https://arxiv.org/abs/2608.07715 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-19T09:13:57.830Z dalla pagina https://arxiv.org/catchup/cs.DS/2026-08-11?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).