twistedcubic / copt

[NeurIPS 2020]. COPT - Coordinated Optimal Transport on Graphs

COPT: Coordinated Optimal Transport for Graph Sketching

COPT is a novel distance metric between graphs defined via an optimization routine, computing a coordinated pair of optimal transport maps simultaneously. This is an unsupervised way to learn general-purpose graph representations, it can be used for both graph sketching and graph comparison.

For a sample run script, please see demo.py. For instance, to sketch a sample graph with 400 training steps and with fixed seed we can run:

python demo.py --seed --n_epochs 400

There are many other options to allow easy custom tuning. To see all command line options, see utils.py[utils.py] or run:

python demo.py --h

For instance, one can run COPT with:

python searchGraph.py --hike --hike_interval 15 python searchGraph.py --hike --hike_interval 15 --grid_search --seed --compress_fac 4

graph.py contains core COPT routines for applications such as graph sketching and comparison. runGraph.py, searchGraph.py, etc contain various applications for COPT.

There is a data directory used by the scripts to write data to. There is some generated sample data provided. Furthermore, if one wishes to generate graph data for other named datasets, one can run the generateData.py script with the dataset name such as:;

python generateData.py --dataset_type real --dataset_name BZR

A corresponding lap.pt data file will be created.

Dependencies

PyTorch 1.1+ numpy networkx netlsd grakel

To install PyTorch, please follow these simple OS-specific instructions.

The other packages can be installed via pip, e.g. python -m pip install numpy networkx grakel netlsd. Or by running

pip install -r requirements.txt

Depending on the functionalities one wishes to run, additional dependencies include: Gromov Wasserstein by Vayer et al, can be placed as "gromov" in directory above this one.

copt's Issues

how to reproduce community discovery experiment

Hi, i have question in reporducing the key alignment experiment both in COPT and GOT. i did this way:

1. use nx.stochastic_block_model to construct a 40-node 4-community graph, where the probs of adding edges within/between communities are 0.9, 0.1 respectively.
2. then i delete 10% edges (about 20) and permute the new graph.
3. use graph.graph_dist(args, plot=False, Ly=Ly, take_ly_exp=False) to calculate COPT distance, and the args here is same as that in utils.parse_args().
4. also use got_stochastic.find_permutaion as in runGraph.perm_mi

However, the nmi is only about 0.5, not nearly 1 like table 2 shows. Now i'm not sure the exact reason, but two guesses:

1. does the probs parameter of nx.stochastic_block_model matters? i noticed that this parameter in utils.create_graph(40, gtype='block', params=params, seed=seed) is [0.97, 0.01, 0.01, 0.01], my case use [0.9, 0.1, 0.1, 0.1].
2. or should we tune some hyper-parameter, while both of COPT and GOT are a little fuzzy in this experiment？like in copt, the args focus on self.optim: lr and hiking.

hope for you reply, thx !