Generalized Metric Repair on Graphs

Anna C. Gilbert, Rishi Sonthalia

Abstract

Many modern data analysis algorithms either assume that or are considerably more efficient if the distances between the data points satisfy a metric. These algorithms include metric learning, clustering, and dimensionality reduction. Because real data sets are noisy, the similarity measures often fail to satisfy a metric. For this reason, Gilbert and Jain [11] and Fan, et al. [8] introduce the closely related problems of sparse metric repair and metric violation distance. The goal of each problem is to repair as few distances as possible to ensure that the distances between the data points satisfy a metric. We generalize these problems so as to no longer require all the distances between the data points. That is, we consider a weighted graph $G$ with corrupted weights $w$ and our goal is to find the smallest number of modifications to the weights so that the resulting weighted graph distances satisfy a metric. This problem is a natural generalization of the sparse metric repair problem and is more flexible as it takes into account different relationships amongst the input data points. As in previous work, we distinguish amongst the types of repairs permitted (decrease, increase, and general repairs). We focus on the increase and general versions and establish hardness results and show the inherent combinatorial structure of the problem. We then show that if we restrict to the case when $G$ is a chordal graph, then the problem is fixed parameter tractable. We also present several classes of approximation algorithms. These include and improve upon previous metric repair algorithms for the special case when $G = K_n$.

Introduction: The Metric Repair Challenge

Many fundamental machine learning tasks, from k-means clustering to manifold learning techniques like Isomap, rely on the assumption that input data distances form a valid metric. A metric must satisfy the triangle inequality: for any three points A, B, and C, the distance $d(A, C)$ cannot exceed the sum $d(A, B) + d(B, C)$.

In practice, real-world data is often corrupted by noise or measurement errors, leading to "broken cycles" where these geometric constraints are violated. Previous research into "Sparse Metric Repair" (SMR) focused on fixing a complete distance matrix (represented as a complete graph $K_n$). This paper introduces the Generalized Graph Metric Repair problem, which extends this task to arbitrary weighted graphs. This generalization is crucial for large-scale datasets where only local relationships are known or where specific structural constraints must be preserved.

A cycle graph illustrating a "broken cycle" where edge weights fail to satisfy metric properties.

Methodology and Structural Insights

The authors analyze three types of repairs: decrease-only (shortening edges), increase-only (lengthening edges), and general (both). Their approach combines complexity analysis with structural graph theory:

  1. Complexity: Using reductions from the Vertex Cover problem, they prove that the problem is generally NP-complete and APX-hard when increases are allowed.
  2. Broken Cycles: They define a "broken cycle" as any cycle where one "top" edge is longer than the sum of the remaining "bottom" edges. A valid repair must modify edges to break every such cycle.
  3. The Chordal Advantage: A key insight is that in chordal graphs (where every cycle of length $\ge 4$ has a chord), any broken cycle implies the existence of a broken 3-cycle (a triangle). This property makes the problem Fixed-Parameter Tractable (FPT) for this class of graphs.
  4. Short Path Cover (SPC): They propose a new combinatorial approximation algorithm that identifies and repairs broken cycles by iteratively computing shortest paths.

Key Results and Performance

The paper establishes that while general graph metric repair is hard, specific constraints and new algorithms offer significant efficiency gains. The "decrease-only" variant remains solvable in $O(n^3)$ time. For chordal graphs, the problem is FPT with a running time of $O((12k^2)^k n^3)$, where $k$ is the number of edits.

The proposed SPC algorithm represents a major step forward in approximation efficiency. As shown in the comparison table below, it achieves a competitive approximation ratio with a significantly lower running time compared to previous state-of-the-art methods.

Comparison of metric repair algorithms, highlighting the improved running time and approximation ratios of the proposed SPC and 5-Cycle Cover methods.

Conclusion and Future Directions

By shifting the focus from complete matrices to general graphs, this work provides a more flexible and efficient framework for data cleaning in machine learning. While the problem remains computationally difficult for arbitrary graph structures, the tractability of chordal graphs and the efficiency of the SPC algorithm offer practical paths forward. Future work may explore tighter approximation bounds and further optimizations for massive datasets where manifold learning is commonly applied.

Summary updated

Abstract

Many modern data analysis algorithms either assume that or are considerably more efficient if the distances between the data points satisfy a metric. These algorithms include metric learning, clustering, and dimensionality reduction. Because real data sets are noisy, the similarity measures often fail to satisfy a metric. For this reason, Gilbert and Jain [11] and Fan, et al. [8] introduce the closely related problems of $\textit{sparse metric repair}$ and $\textit{metric violation distance}$. The goal of each problem is to repair as few distances as possible to ensure that the distances between the data points satisfy a metric. We generalize these problems so as to no longer require all the distances between the data points. That is, we consider a weighted graph $G$ with corrupted weights w and our goal is to find the smallest number of modifications to the weights so that the resulting weighted graph distances satisfy a metric. This problem is a natural generalization of the sparse metric repair problem and is more flexible as it takes into account different relationships amongst the input data points. As in previous work, we distinguish amongst the types of repairs permitted (decrease, increase, and general repairs). We focus on the increase and general versions and establish hardness results and show the inherent combinatorial structure of the problem. We then show that if we restrict to the case when $G$ is a chordal graph, then the problem is fixed parameter tractable. We also present several classes of approximation algorithms. These include and improve upon previous metric repair algorithms for the special case when $G = K_n$
BibTeX
@inproceedings{gilbert2020generalized,
  author = {Anna C. Gilbert and Rishi Sonthalia},
  title = {{Generalized Metric Repair on Graphs}},
  booktitle = {SWAT},
  year = {2020},
  url = {https://openreview.net/forum?id=XUjEX2xt1DM},
}
Figure