Skip to content
/ FGW Public

Code for Optimal Transport for structured data with application on graphs

Notifications You must be signed in to change notification settings

tvayer/FGW

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

31 Commits
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

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 ?

  • cleaning of k-means of multiple graphs
  • 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

About

Code for Optimal Transport for structured data with application on graphs

Resources

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published

Languages