trneedham/Spectral-Gromov-Wasserstein

Graph matching and clustering by comparing heat kernels via optimal transport.

Generalized Spectral Clustering via Gromov-Wasserstein Learning

This repository implements Generalized Spectral Clustering via Gromov-Wasserstein Learning (AISTATS 2021).

Requirements

We highly recommend setting up a virtual environment using conda to test this code, and then installing dependencies using the provided requirements.txt file:

conda create -n 2020-sgw-test python=3.6
conda activate 2020-sgw-test
pip install -r requirements.txt

Next, please go into the data folder and unzip the REDDIT-BINARY and COLLAB files to obtain:

data/REDDIT-BINARY/REDDIT-BINARY*.txt
data/COLLAB/COLLAB*.txt

Evaluate prepared scripts

To replicate the results provided in the paper, simply run the bash script:

chmod u+x submit.sh
./submit.sh

It may take several hours to generate all the results files. These will be stored in the base folder as res_*.txt and res_*.pdf. The shell script also includes individual commands that you can run separately.

Mapping between scripts and tables/figures in paper

Script	Table or Figure
plot_matchings.py	Figure 1
plot_energy.py	Table 1, Figure 3
plot_node_correctness.py	Table 2
sbmAmiModularity.py	Figure 2
randomGraphPartitioning.py	Table 3
partition*.py	Tables 4-6
supervisedPartitionExperiment.py	Figure 5
hkscaleCouplings.py	Figures 6-7
plot_gwa_village.py	Figure 8

References

We describe full references in the paper. A list with links is provided below

Data:

• Stanford SNAP collection
• Benchmark datasets for graph kernels

Modules

• Python Optimal Transport library
• Scalable Gromov-Wasserstein Learning
  • DataIO.py, EvaluationMeasure.py, GromovWassersteinFramework.py, GromovWassersteinGraphToolkit.py
• Gromov-Wasserstein Statistics
  • gromovWassersteinAveraging.py, gwaTools.py, geodesicVisualization.py
• Infomap
• Scikit-learn

License

This work is covered under an MIT license.