  We address the problem of merging graph and feature-space information while
learning a metric from structured data. Existing algorithms tackle the problem
in an asymmetric way, by either extracting vectorized summaries of the graph
structure or adding hard constraints to feature-space algorithms. Following a
different path, we define a metric regression scheme where we train
metric-constrained linear combinations of dissimilarity matrices. The idea is
that the input matrices can be pre-computed dissimilarity measures obtained
from any kind of available data (e.g. node attributes or edge structure). As
the model inputs are distance measures, we do not need to assume the existence
of any underlying feature space. Main challenge is that metric constraints
(especially positive-definiteness and sub-additivity), are not automatically
respected if, for example, the coefficients of the linear combination are
allowed to be negative. Both positive and sub-additive constraints are linear
inequalities, but the computational complexity of imposing them scales as
O(D3), where D is the size of the input matrices (i.e. the size of the data
set). This becomes quickly prohibitive, even when D is relatively small. We
propose a new graph-based technique for optimizing under such constraints and
show that, in some cases, our approach may reduce the original computational
complexity of the optimization process by one order of magnitude. Contrarily to
existing methods, our scheme applies to any (possibly non-convex)
metric-constrained objective function.
