Skip to content
Code for Optimal Transport for structured data with application on graphs
Python
Branch: master
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Type Name Latest commit message Commit time
Failed to load latest commit information.
data First work May 5, 2019
examples
lib
README.md bib May 26, 2019
barycircle.png
coupling_on_1D.png
coupling_on_graphs.png

README.md

FGW

Python3 implementation of the paper Optimal Transport for structured data with application on graphs

Fused Gromov-Wasserstein (FGW) is a distance between labeled graphs based on Optimal Transport. It is applicable between graphs with different number of nodes and with any type of label/feature on the nodes.

It computes a soft assignment of the nodes wrt their features and the graphs' structures. It can be used for visualisation, classification and barycenter of multiple graphs.

In the paper we also used this implementation of the Patchy-San Convolutional Network framework PSCN

Feel free to ask if any question

If you use this toolbox in your research and find it useful, please cite FGW using the following bibtex reference:

@InProceedings{vay2019fgw,
  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},
  address =    {Long Beach, California, USA},
  month =    {09--15 Jun},
  publisher =    {PMLR},
  pdf =    {http://proceedings.mlr.press/v97/titouan19a/titouan19a.pdf},
  url =    {http://proceedings.mlr.press/v97/titouan19a.html}
}

Prerequisites

  • For graph tools networkx Networkx (>=2.0)
  • For the classification using Graph Kernels using GraKel GraKel (>=0.1a5)
  • For Optimal transport Python Optimal Transport POT (>=0.5.1)
  • Sklearn (>=0.20.0)
  • Numpy (>=1.11)
  • Scipy (>=1.0)
  • Cython (>=0.23)
  • Matplotlib (>=1.5)

Data

All the data used in the paper came from the Benchmark Data Sets for Graph Kernels [3]

What is included ?

  • FGW between structured objects with a cost M between features and structure matrices C1,C2:

Alt text

  • Comparing labeled graphs using FGW:

  • Methods for graphs barycenter using FGW:

Alt text

  • Nested cross validation used in the paper (for e.g):
python3 nested_cv_fgw.py -dn mutag -d ../data -r ../results -ni 10 -no 50  -fea hamming_dist -st shortest_path -cva True -wl 2 
  • Some demos are presented in the notebooks ("examples" folder):

What will be added ?

  • k-means of multiple graphs
  • Integration in the POT library [1] of FGW
  • Add other methods for graph kernels

Authors

References

[1] Flamary Rémi and Courty Nicolas POT Python Optimal Transport library

[2] Siglidis, Giannis and Nikolentzos, Giannis and Limnios, Stratis and Giatsidis, Christos and Skianis, Konstantinos and Vazirgiannis, Michali. GraKeL: A Graph Kernel Library in Python

[3] Kristian Kersting and Nils M. Kriege and Christopher Morris and Petra Mutzel and Marion Neumann Benchmark Data Sets for Graph Kernels

You can’t perform that action at this time.