Optimal Transport for structured data with application on graphs

Vayer Titouan, Nicolas Courty, Romain Tavenard, Chapel Laetitia, Rémi Flamary
Proceedings of the 36th International Conference on Machine Learning, PMLR 97:6275-6284, 2019.

Abstract

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{é}chet means or barycenters of graphs are illustrated and discussed in a clustering context.

Cite this Paper

BibTeX
@InProceedings{pmlr-v97-titouan19a, title = {Optimal Transport for structured data with application on graphs}, author = {Titouan, Vayer and Courty, Nicolas and Tavenard, Romain and Laetitia, Chapel and Flamary, R{\'e}mi}, booktitle = {Proceedings of the 36th International Conference on Machine Learning}, pages = {6275--6284}, year = {2019}, editor = {Chaudhuri, Kamalika and Salakhutdinov, Ruslan}, volume = {97}, series = {Proceedings of Machine Learning Research}, month = {09--15 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v97/titouan19a/titouan19a.pdf}, url = {https://proceedings.mlr.press/v97/titouan19a.html}, abstract = {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{é}chet means or barycenters of graphs are illustrated and discussed in a clustering context.} }
Endnote
%0 Conference Paper %T Optimal Transport for structured data with application on graphs %A Vayer Titouan %A Nicolas Courty %A Romain Tavenard %A Chapel Laetitia %A Rémi Flamary %B Proceedings of the 36th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2019 %E Kamalika Chaudhuri %E Ruslan Salakhutdinov %F pmlr-v97-titouan19a %I PMLR %P 6275--6284 %U https://proceedings.mlr.press/v97/titouan19a.html %V 97 %X 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{é}chet means or barycenters of graphs are illustrated and discussed in a clustering context.
APA
Titouan, V., Courty, N., Tavenard, R., Laetitia, C. & Flamary, R.. (2019). Optimal Transport for structured data with application on graphs. Proceedings of the 36th International Conference on Machine Learning, in Proceedings of Machine Learning Research 97:6275-6284 Available from https://proceedings.mlr.press/v97/titouan19a.html.

Related Material