Optimal Transport for structured data with application on graphs
Titouan Vayer · Nicolas Courty · Romain Tavenard · Chapel Laetitia · Remi Flamary

Tue Jun 11th 02:30 -- 02:35 PM @ Seaside Ballroom

This work considers the problem of computing distances between structured objects such as undirected graphs, seen as probability distributions in a specific metric space. We consider a new transportation distance ( i.e. that minimizes a total cost of transporting probability masses) that unveils the geometric nature of the structured objects space. Unlike Wasserstein or Gromov-Wasserstein metrics that focus solely and respectively on features (by considering a metric in the feature space) or structure (by seeing structure as a metric space), our new distance exploits jointly both information, and is consequently called Fused Gromov-Wasserstein (FGW). After discussing its properties and computational aspects, we show results on a graph classification task, where our method outperforms both graph kernels and deep graph convolutional networks. Exploiting further on the metric properties of FGW, interesting geometric objects such as Fr{\'e}chet means or barycenters of graphs are illustrated and discussed in a clustering context.

Author Information

Titouan Vayer (IRISA)
Nicolas Courty (IRISA, Universite Bretagne-Sud)
Romain Tavenard (LETG-Rennes / IRISA-Obelix)
Chapel Laetitia (IRISA)
Remi Flamary (Université côte d'Azur)

Related Events (a corresponding poster, oral, or spotlight)