Ordinally Consensus Subset over Multiple Metrics

In recent years, there have been many studies on data sets with multiple views, which can contain different sets of features from multiple sources carrying different types of information. For example, consider neuron cells in the field of neuroscience [15]. A single neuron cell could have both morphology features and RNA-sequencing information available. Simply concatenating these two types of feature sets and applying a classical single-view method may not produce meaningful results – The types of features may be different, and it is not clear how to properly weigh them when combined. Instead, there have been many approaches developed to handle multi-view data. For example, Lashkari and Golland [14], Bickel and Scheffer [4] considered using EM algorithm and (convex) mixture model on multi-view clustering; Kumar, Rai and Hal [13] and Cai et al. [5] extended spectral clustering algorithm for multi-view data. See also surveys on multi-view clustering [6], and more broadly, on multi-view learning [16].

Very often in applications, multiple views give rise to multiple metrics $\{{\rho}_{1},\ldots\\ ,{\rho}_{k}\}$ over the same data set $X$. Our goal is to study whether these metrics are “consistent” over $X$, and identify a largest subset $X^{\prime}$ of $X$, called consensus, over which these input metrics are “consistent”. However, when comparing these metrics, note that the precise distance values between points in $X$ induced by different ${\rho}_{i}$s may not have the same meaning, two metrics may not have simple, say, linear relation between them, and thus the distance values are not readily comparable (even after normalization). For example, the distance between two neuron cells based on their tree morphology can be very different from that based on their gene expression profiles. Hence in this paper, we will compute consensus under multiple metrics based on ordinal information, namely the order of pairwise distances under each metric.

More specifically, given a metric system $(\mathcal{M},X)$, consisting of a set of $k$ input metrics $\mathcal{M}=\{{\rho}_{1},...,{\rho}_{k}\}$ on a discrete data set $X$ with cardinality $n$, we propose to study the problem of finding maximum ordinal consensus of $X$ w.r.t. $\mathcal{M}$. Specifically, we aim to find a maximum subset $X^{\prime}\subset X$, such that all metrics will have consistent pairwise distances if restricted on node set $X^{\prime}$. We also call $S=X\setminus X^{\prime}$ as outliers, while $X^{\prime}$ is our targeted ordinal consensus. The dual problem is to find the minimum inconsistent (outlier) set $S$ such that all metrics are consistent when restricted to the subset $X\setminus S$.

Note that the maximum (ordinal) consensus subset and the minimum inconsistent subset are equivalent. In Section 3 and 4, we will show for both the strong and weak consistency definitions, finding the subset $S$ over an input of a constant number of (two for the strong case, and three for the weak case) ultrametrics or Euclidean metrics on the real line are NP-hard. These special cases imply that the problems are NP-hard if the inputs are arbitrary metrics. We also study the approximation algorithms for both the strongly and weakly minimum inconsistent subset problems. In particular, for the strongly inconsistent subset, we propose a 4-approximation algorithm with time complexity $O(kn^{2}\log n)$. For the weak case, we have a $O(n^{6})$-time 6-approximation algorithm. See Appendix A.10 for a table summarizing our hardness results and approximation algorithms.

All missing technical details can be found in the appendix.

These definitions of consistency over trees however are not identical from the ordinal consistency we propose. These problems are related to, but still different from, our maximum ordinal consensus problem if the input metrics are ultrametrics. An ultrametric can be represented by a corresponding representing tree where each tree node has a height value. Finding a strong consensus $S$ is equivalent to finding a subset of leaf nodes such that the restricted subtrees are not only isomorphic, but also the heights of all internal nodes must have the same order – This height condition appears to make the problem much harder: While the MAST problem on two trees can be solved in polynomial time via dynamic programming, the ordinal consensus problem is NP-hard even for only two ultrametrics, as we will show in Section 3.

The input is a metric system $(\mathcal{M};X)$, consisting of a set of $k$ metrics $\mathcal{M}=\{{\rho}_{1},{\rho}_{2},...,{\rho}_{k}\}$ over the point set $X=\{x_{1},...,x_{n}\}$. For any $i\in[1,k]$, ${\rho}_{i}(x,x^{\prime})$ is the distance between point $x,x^{\prime}\in X$ w.r.t. ${\rho}_{i}$. Our goal is to find a minimum subset $S\subset X$, such that the order of all pairwise distance restricted on $X\backslash S$ are consistent under a certain definition. Below we first introduce two notions of consistency. The two optimization problems we will study are given in Definition 2.6.

Other than strong consistency, we also consider a weaker notion of consistency: In particular, we now only require that the order constructed by taking the plurality voting¹¹1In plurality voting, a candidate wins if it has the most votes than the other candidates. It does not have to get a majority (more than 50%) of the votes. over all input metrics is valid. To define the weak consistency formally, we will first define the so-called relation set and the auxiliary graph.

For example, the relation $(x_{p},x_{q})<(x_{r},x_{s})\in\mathcal{R}$ if and only if this relation appears in more (or the same number of) metrics than the other two relations ($``="$, $``<"$).

The relation set constructed above may be not “valid” in the sense that no single metric can generate those relations. To check the validity of this relation set, we now define a specific auxiliary graph $\mathcal{G}$, whose nodes correspond to pairs of points from $X$. There are three different connections between two graph nodes, which correspond to the three possible relations between their corresponding pairs in the relation set $\mathcal{R}$. We will use this graph later to decide whether $\mathcal{R}$ is valid or not.

We will use $v_{1},...,v_{N}$ (corresponding to all pairs in $X$) to represent nodes in graph $\mathcal{G}$, where $N={n\choose 2}$ if $n=|X|$. The auxiliary graph $G$ is a fully connected mixed graph (i.e., every pair of distinct vertices is connected by a unique edge, and the edge can be directed or undirected) with one edge between every two nodes. We say $v_{i}>v_{j}$ (or $``="$ or $``<"$) if there is a directed edge from $v_{i}$ to $v_{j}$ (or an undirected edge between them, or a directed edge from $v_{j}$ to $v_{i}$), which means the pair, say $(x,y)\in X\times X$, represented by $v_{i}$ has a larger pairwise distance compared with the pair represented by $v_{j}$. A cycle in a mixed graph can be formed by a mixture of directed edges and undirected edges. Intuitively, suppose we have a completely directed cycle like the one shown in Figure 1 (a), then there is a conflict in the relations for pairwise distances, as $v_{1}<v_{2}<v_{3}<v_{4}<v_{1}$. Hence the relation set $\mathcal{R}$ will not be valid in this case. There are more types of “directed” cycles and they can cause such conflict. In particular:

We say that a metric $\widehat{{\rho}}$ generates a relation set $\mathcal{R}$, if the order of any two pairwise distances induced by $\widehat{{\rho}}$ are the same as in $\mathcal{R}$. In this case, we say the relation set $\mathcal{R}$ is valid. The following result provides a simple characterization for a valid relation set by using its corresponding auxiliary graph.

We are now ready to define the weak consistency.

The optimization problems we aim to study in this paper are defined as follows.

Note that minimizing the inconsistent set is equivalent to maximizing the consensus (although their approximation may not be equivalent).

The decision version of Strong-MIS (and Weak-MIS) problem is as follows: Given $\mathcal{M},X$ and also an integer $a$. Is there a subset $S\subset X$ with $|S|=a$ such that $\mathcal{M}$ restricted on $X\backslash S$ are strongly consistent (resp. weakly consistent)?

We will show in Section 3 and 4 that the decision versions of Strong-MIS and Weak-MIS are in NP (see lemma 3.1 and lemma 4.1). Thus in most proofs, we will only show NP-hardness via reductions from NP-hard problems. The NP-completeness naturally follows by the fact that both decision problems are in NP.

In this section, we will study the Strong-MIS problem. Specifically, we show in Theorem 3.1 and 3.2 that the decision version of the Strong-MIS problem is NP-complete even when the input metric spaces are restricted to two very simple cases: the line metrics and the ultrametrics. Corollary 3.1 gives an inapproximability result. To complement that, in Theorem 3.4, we provide a $4$-approximation algorithm for the general case.

Intuitively, finding the minimum strongly inconsistent set has a similar flavor as Minimum Vertex Cover or Minimum Hitting Set [10]. Intuitively, in Strong-MIS problem, given data points $X$, a quartet $(x_{p},x_{q},x_{r},x_{s})$ will be a target set if they induce a conflict between any two input metrics, and the goal is to find a Minimum Hitting Set $\mathcal{H}$ such that for all target sets, at least one element is in $\mathcal{H}$. However, to show that Strong-MIS remains hard even for special simple metrics, we need to construct reductions carefully, and sometimes need to use different NP-complete problems to reduce from. We include the list of NP-complete problems used for reductions in Appendix B.

To study Strong-MIS, we first define the so-called Conflict Set, which will be used frequently in NP-hardness proofs.

It is clear that the decision version of Strong-MIS is in NP as stated in the following lemma.

It turns out that the decision version of Strong-MIS is weakly NP-complete (which allows the magnitude of data involved to be exponential) even if we restrict the input metrics to be only two line metrics. The proof is in Appendix A.2.

The following theorem shows that even with only 2 ultrametrics, finding a Strong-MIS remains NP-hard. The proof uses a reduction from Max 2-SAT problem; it is non-trivial and can be found in Appendix A.3.

The hardness result on 2 ultrametrics implies that finding Strong-MIS is also NP-hard when the input is two arbitrary metrics. The result is stated below. This theorem can also be proven directly via a reduction from Minimum Vertex Cover, which for completeness we include the simple details in Appendix A.4.

In fact, the proof in Appendix A.4 gives a size-preserving reduction. Hence the Corollary below follows directly from the inapproximability result [12] for Minimum Vertex Cover.

We now focus on the Weak-MIS problem of finding a minimum weakly inconsistent subset. In Theorems 4.1 and 4.2, we show that it is NP-complete for the special case of only three input line metrics or ultrametrics. We provide a straightforward 6-approximation algorithm at the end.

By definition 2.5 and 2.6, if $X\backslash S$ is a consensus set, then the auxiliary graph $\mathcal{G}$ restricted on $X\backslash S$ must contain no directed cycle. It is well known that a tournament (fully connected directed graph) has a directed cycle if and only if it has a directed triangle [7]. It turns out that a similar result holds for auxiliary graphs, which are mixed graphs: see the claim below. See Figure 2 for the 3 possible cases of directed triangles. The simple proof of this claim can be found in Appendix A.6.

Hence to see whether there is any directed cycle in the auxiliary graph, one only needs to check if there is any directed triangle.

Followed by claim 4.1, the decision version of Weak-MIS is in NP.

When there are two metrics, with the tie-breaking rule defined in Definition 2.2, it is clear that we would always prefer the first metric (once the order of input metrics is fixed). Thus in this case, the minimum inconsistent set is simply $\emptyset$. The problem of Weak-MIS becomes non-trivial when there are three metrics.

Our first main result is as follows, with proof in Appendix A.7.

Our second main result is the hardness for ultrametrics.

The following theorem is an implication from the previous proof. Similarly as Strong-MIS, we also provide a direct proof for arbitrary metrics in Appendix A.9. In the proof, we construct a size-preserving reduction from Minimum Vertex Cover which again leads to an $(2-\epsilon)$-inapproximability result.

Finally, there is a simple 6-approximation algorithm with running time $O(n^{6})$: Specifically, given a metric system $(\mathcal{M};X)$ with $n=|X|$, we first build auxiliary graph $\mathcal{G}$ as described earlier in $O(kn^{4})$ time. We want to construct an outlier set $S\subset X$ so that it “hits” all directed triangles in $\mathcal{G}$: note that this will then guarantee that $X\setminus S$ is a consensus set w.r.t. $\mathcal{M}$. To this end, we simply enumerate all directed triangles in $\mathcal{G}$ in $O(n^{6})$ time. We then initialize $S=\emptyset$ and go through the list of directed triangles one by one. For each directed triangle $\Delta w_{1}w_{2}w_{3}$ (where each $w_{i}$ is a pair of points in $X$), if $S$ does not intersect with any of the points included in $w_{1}\cup w_{2}\cup w_{3}\subset X$, then we simply add all these points (at most 6 distinct points) to $S$. Otherwise, this triangle is already “hit” by $S$ and we do nothing. Let $S^{*}$ be the minimum weakly inconsistent set (i,e, the optimal solution for Weak-MIS). It is easy to see that $|S^{*}|\geq|S|/6$, as all the 6-tuples (at most 6) we ever added to $S$ are all disjoint, and for each such 6-tuple, $S^{*}$ must contain at least one point from it. Furthermore, it is also easy to see that after removing all points $S$, the resulting auxiliary graph restricted to only pairs not containing points in $S$ is free of directed triangles, and thus free of directed cycles by Lemma 2.1 and Claim 4.1. Hence $X\setminus S$ is a consensus set w.r.t. $\mathcal{M}$, and $|S|\leq 6|S^{*}|$. Hence:

In this paper, we proposed to study the maximum ordinal consensus problem over a set of input metrics. We developed two concepts of “consistency” that only rely on ordinal information of pairwise distances. We proved several hardness results for both definitions with different input metrics. We also developed constant-factor approximation algorithms for the minimum inconsistent set problem under both definitions.

There are still some open directions for future work. For example, can we close the gap between the inapproximability and the approximation algorithm we developed? Can we improve the time complexity, especially for the Weak-MIS problem? Can we find better approximation algorithms for special cases such as Euclidean metrics or ultrametrics? We also note that the current approximation algorithms target the minimum (ordinally) inconsistent subset problems – how about the dual maximum ordinal consensus problem?

This work is partially supported by National Science Foundation (NSF) under grant IIS-1815697, as well as National Institute of Health (NIH) under grant R01EB022899.