Non-metric label propagation

In many applications non-metric distances are bet-ter than metric distances in reflecting the percep-tual distances of human beings. Previous studies on non-metric distances mainly focused on super-vised setting and did not consider the usefulness of unlabeled data. In this paper, we present probably the first study of label propagation on graphs in-duced from non-metric distances. The challenge here lies in the fact that the triangular inequality does not hold for non-metric distances and there-fore, a direct application of existing label propa-gation methods will lead to inconsistency and con-flict. We show that by applying spectrum transfor-mation, non-metric distances can be converted into metric ones, and thus label propagation can be ex-ecuted. Such methods, however, suffer from the change of original semantic relations. As a main result of this paper, we prove that any non-metric distance matrix can be decomposed into two met-ric distance matrices containing different informa-tion of the data. Based on this recognition, our pro-posed NMLP method derives two graphs from the original non-metric distance and performs a joint label propagation on the joint graph. Experiments validate the effectiveness of the proposed NMLP method.