One coupling that has to satisfy the features and the structure at once

A labelled graph carries two kinds of information, and the two usual distances each throw one away: Wasserstein on the labels ignores the edges, Gromov-Wasserstein on the edges ignores the labels. Fusing them forces a single plan to explain both, and alpha says which evidence dominates. Solved by conditional gradient with an exact transport step, so no entropic blur enters the plan.

Usage

Otfgw(M, Cx, Cy, a, b, alpha = 0.5, max_iter = 20)

Arguments

M

Feature cost between the two vertex sets, n by m.

Cx

Structure matrix of the first object, n by n.

Cy

Structure matrix of the second object, m by m.

a, b

Marginals.

alpha

Trade-off in [0, 1].

max_iter

Conditional-gradient steps.

Value

List with T, cost, wass_part, gromov_part, n, m, iters.

Details

Formula: \(min_T (1-alpha) <T, M> + alpha sum_ijkl |Cx_ik - Cy_jl|^2 T_ij T_kl\) – Vayer et al. (2020) eq. (3). The linearised cost is (1-alpha) M - 4 alpha Cx T Cy and the step is gamma = 2/(k+2).

References

Vayer, T., Chapel, L., Flamary, R., Tavenard, R. and Courty, N. (2020). Algorithms 13(9):212. doi:10.3390/a13090212 .

Examples

M <- matrix(c(0, 1, 1, 0), 2)
Cx <- matrix(c(0, 1, 1, 0), 2)
r <- Otfgw(M, Cx, Cx, a = c(0.5, 0.5), b = c(0.5, 0.5), alpha = 0.5)
round(r$T, 3)
#>      [,1] [,2]
#> [1,]  0.5  0.0
#> [2,]  0.0  0.5