Generalized Metric Repair on Graphs

Chenglin Fan, Anna C. Gilbert, Benjamin Raichel, Rishi Sonthalia, Gregory Van Buskirk

Abstract

Metric spaces are fundamental to many data analysis tasks, including clustering and dimensionality reduction. However, real-world data often contains noise that violates the triangle inequality. This paper investigates the Generalized Metric Repair problem, where the goal is to modify the minimum number of edge weights in a general graph to satisfy a metric. We establish that the problem is APX-hard via a reduction from MULTICUT and provide several approximation algorithms. Furthermore, we show that the problem is fixed-parameter tractable (FPT) for the class of $\varsigma$-chordal graphs.

Introduction

In a metric space, the distance between any two points $u$ and $v$ must satisfy the triangle inequality: $d(u, v) \leq d(u, w) + d(w, v)$ for any intermediate point $w$. When data is collected from noisy sensors or incomplete observations, these constraints are frequently violated. Previous work on "Sparse Metric Repair" focused on complete graphs, where every pair of points has a defined distance. This paper generalizes the problem to arbitrary weighted graphs $G = (V, E, w)$, allowing for more flexible modeling of sparse datasets where only specific relationships are known.

Structural Characterization: Broken Cycles

The core of the metric repair problem lies in identifying and fixing "broken cycles." A cycle is considered broken if it contains an edge (the "heavy" edge) whose weight exceeds the sum of the weights of all other edges in the cycle. The difference between the heavy edge's weight and the path sum is called the deficit. A graph satisfies a metric if and only if it contains no broken cycles.

To determine if a proposed set of edge modifications $S$ successfully repairs the graph, the authors utilize a verification procedure.

The VERIFIER algorithm determines if a set of edges $S$ constitutes a valid repair for the graph $G$.

As shown in the VERIFIER algorithm, a set $S$ is valid if, after setting the weights of edges in $S$ to a sufficiently large value $M$ and recomputing shortest paths, only the weights of edges originally in $S$ are altered. This structural insight allows the problem to be framed as a covering problem over the set of broken cycles.

Hardness and the MULTICUT Connection

A key contribution of this work is establishing the computational complexity of generalized metric repair. The authors provide an approximation-preserving reduction from the MULTICUT problem. This reduction implies that metric repair is APX-hard. Furthermore, under the Unique Games Conjecture, the problem cannot be approximated within any constant factor, highlighting a significant jump in difficulty from the complete graph case.

Algorithmic Results

Despite the hardness results, the paper presents several positive algorithmic outcomes:

  1. $(L+1)$-Approximation: By viewing the problem as a hitting set problem on broken cycles, the authors achieve an approximation ratio tied to $L$, the maximum number of edges in any broken cycle.
  2. $O(\kappa \log n)$-Approximation: The authors introduce an algorithm whose performance depends on $\kappa$, the number of distinct deficit values in the graph. This is particularly useful when the noise follows specific patterns.
  3. Complexity Improvements for Complete Graphs: For the specific case of complete graphs ($K_n$), the authors improved the runtime analysis of existing algorithms from $O(n^6)$ to $O(n^5)$.
  4. FPT for $\varsigma$-chordal Graphs: For graphs where the largest chordless cycle has a bounded size $\varsigma$, the problem is shown to be fixed-parameter tractable when parameterized by the size of the optimal solution ($OPT$). This provides an efficient solution for a broad and practically relevant class of graphs.

Conclusion

By generalizing metric repair to arbitrary graphs, this work bridges the gap between theoretical metric properties and practical, sparse data analysis. The connection to MULTICUT provides a deep understanding of the problem's complexity, while the new approximation and FPT algorithms offer viable paths for handling metric violations in structured datasets. Future research may explore whether the dependence on the deficit count $\kappa$ can be further reduced or if it represents a fundamental limit of the problem.

Summary updated

Abstract

Many modern data analysis algorithms either assume or are considerably more efficient if the distances between the data points satisfy a metric. These algorithms include metric learning, clustering, and dimension reduction. As real data sets are noisy, distances often fail to satisfy a metric. For this reason, Gilbert and Jain and Fan et al. introduced the closely related sparse metric repair and metric violation distance problems. The goal of these problems is to repair as few distances as possible to ensure they satisfy a metric. Three variants were considered, one admitting a polynomial time algorithm. The other variants were shown to be APX-hard, and an $O(OPT^{1/3})$-approximation was given, where $OPT$ is the optimal solution size. In this paper, we generalize these problems to no longer consider all 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 weight modifications so that the resulting weighted graph distances satisfy a metric. This is a natural generalization and is more flexible as it takes into account different relationships among the data points. As in previous work, we distinguish among the types of repairs permitted and focus on the increase only and general versions. We demonstrate the inherent combinatorial structure of the problem, and give an approximation-preserving reduction from MULTICUT. Conversely, we show that for any fixed constant $\varsigma$, for the large class of $\varsigma$-chordal graphs, the problems are fixed parameter tractable. Call a cycle broken if it contains an edge whose weight is larger than the sum of all its other edges, and call the amount of this difference its deficit. We present approximation algorithms, one which depends on the maximum number of edges in a broken cycle, and one which depends on the number of distinct deficit values.
BibTeX
@inproceedings{fan2020generalized,
  author = {Chenglin Fan and Anna C. Gilbert and Benjamin Raichel and Rishi Sonthalia and Gregory Van Buskirk},
  title = {{Generalized Metric Repair on Graphs}},
  booktitle = {SWAT},
  year = {2020},
  url = {https://openreview.net/forum?id=XUjEX2xt1DM},
}
Figure