  Graphs are used in almost every scientific discipline to express relations
among a set of objects. Algorithms that compare graphs, and output a closeness
score, or a correspondence among their nodes, are thus extremely important.
Despite the large amount of work done, many of the scalable algorithms to
compare graphs do not produce closeness scores that satisfy the intuitive
properties of metrics. This is problematic since non-metrics are known to
degrade the performance of algorithms such as distance-based clustering of
graphs (Stratis and Bento 2018). On the other hand, the use of metrics
increases the performance of several machine learning tasks (Indyk et al. 1999,
Clarkson et al. 1999, Angiulli et al. 2002, Ackermann et al. 2010). In this
paper, we introduce a new family of multi-distances (a distance between more
than two elements) that satisfies a generalization of the properties of metrics
to multiple elements. In the context of comparing graphs, we are the first to
show the existence of multi-distances that simultaneously incorporate the
useful property of alignment consistency (Nguyen et al. 2011), and a
generalized metric property. Furthermore, we show that these multi-distances
can be relaxed to convex optimization problems, without losing the generalized
metric property.
