Generalized Metric Repair on Graphs

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 talk, I will 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. I will demonstrate the inherent combinatorial structure of the problem, and present a few theorems about the hardness of the problem. I will also show that for any fixed constant ς, for the large class of ς-chordal graphs, the problems are fixed parameter tractable. Time permitting, I will then discuss a variant of this problem where we are not given the graph $G$, but learn its structure as well.