sympa: Symmetric Spaces for Graph Embeddings

Code for the papers "Symmetric Spaces for Graph Embeddings: A Finsler-Riemannian Approach" published at ICML 2021, and the paper "Hermitian Symmetric Spaces for Graph Embeddings" published at DiffGeo4DL @ NeurIPS 2020.

Available Models

Vector models:

euclidean
poincare
lorentz
sphere
prod-hysph: Product of hyperbolic x sphere
prod-hyhy: Product of hyperbolic x hyperbolic
prod-hyeu: Product of hyperbolic x euclidean

Matrix models:

spd: Symmetric positive definite matrices space
upper: Upper half space model of the Siegel space
bounded: Bounded domain model of the Siegel space
dual: Compact dual

The last three allow different metrics

Available metrics

riem: Riemannian metric
fone: Finsler One
finf: Finsler Infinity
fmin: Finsler metric of minimum entropy
wsum: Learns weights for a weighted sum of the vector-valued distance

Requirements

Python == 3.7
Pytorch == 1.5.1: conda install pytorch==1.5.1 torchvision==0.6.1 [cpuonly | cudatoolkit=10.2] -c pytorch. In CPU environments, data parallel is not stable with pytorch >= 1.6
Geoopt >= 0.3.1: install from repository is advised: pip install git+https://github.com/geoopt/geoopt.git
XiTorch: for working with the compact dual only
networkx and networkit: for preprocessing only
matplotlib: for preprocessing only
tensorboardx
tqdm

Running experiments

1. Preprocess Data

In all preprocessing cases, the option --run_id=RUN_ID is required. The data will be saved in data/RUN_ID. If --plot_graph is passed, a plot will be generated, but the plotting can take a long time if the graph is large.

Grids:

python preprocess.py --graph=grid --grid_dims=DIMS --nodes=NODES --run_id=RUN_ID

It will create a grid of DIMS dimensions with int(NODES^(1/DIMS)) nodes.
Ex: python preprocess.py --graph=grid --grid_dims=3 --nodes=27 will create a 3x3x3 cube graph

Trees

python preprocess.py --graph=tree --tree_branching=BRANCHING --tree_height=HEIGHT --run_id=RUN_ID

It will create a tree with branching factor BRANCHING and height HEIGHT.

Cartesian or Rooted products

By default it will create a cartesian/rooted product of a tree and a grid, but it can be modified by changing the order in the code

python preprocess.py --graph=product-cartesian --grid_dims=DIMS --nodes=NODES --tree_branching=BRANCHING --tree_height=HEIGHT --run_id=RUN_ID

It will create a cartesian (rooted with --graph=product-rooted) product of the specified tree and grid.

Social Networks

python preprocess.py --graph=TYPE --run_id=RUN_ID

Current available options are social-karate, social-davis, social-florentine, social-miserables. See NetworkX doc

Expanders

python preprocess.py --graph=TYPE --nodes=NODES --run_id=RUN_ID

Current available options are expander-margulis, expander-chordal, expander-paley. See NetworkX expanders doc

Custom

python preprocess.py --graph=NAME --run_id=RUN_ID

It will look for a file in data/NAME/NAME.edges where the graph should be represented as:

src_node1 dst_node1 [weight1]
src_node2 dst_node2 [weight2]
...

where src_node and dst_node are int values and weight is an optional float value.

2. Train Graph Embeddings

python -m torch.distributed.launch --nproc_per_node=N_CPUS --master_port=2055 train.py \\
            --n_procs=N_CPUS \\
            --data=PREP \\
            --run_id=RUN_ID \\
            --results_file=out/results.csv \\
            --model=MODEL \\
            --metric=riem \\
            --dims=4 \\
            --learning_rate=1e-2 \\
            --val_every=25 \\
            --patience=50 \\
            --max_grad_norm=100 \\
            --batch_size=2048 \\
            --epochs=1000

Experiments can be run distributed over multiple CPUs/GPUs with N_CPUS. PREP must be the name of the graph to embed (what in step 1 was called RUN_ID). Results will be reported in results_file with run_id as the name. For model and metric see Available Models

Considerations

The method inner is implemented for both the Upper Half space and the Bounded domain model. With this, experiments can be run with RiemannianAdam. However, we found them to be very unstable, therefore all experiments reported in the paper were run with RiemannianSGD

TODO

Fix broken tests
Add Finsler Metrics to SPD manifold
Merge branch with Recommender System experiments into master
Merge branch with ploting tools into master

Citation

The source code and data in this repository aims at facilitating the study of graph embeddings in symmetric spaces. If you use the code/data, please cite it as follows:

@InProceedings{lopez2021symmetric,
  title =    {Symmetric Spaces for Graph Embeddings: A Finsler-Riemannian Approach},
  author =       {L\'opez, Federico and Pozzetti, Beatrice and Trettel, Steve and Strube, Michael and Wienhard, Anna},
  booktitle =    {Proceedings of the 38th International Conference on Machine Learning},
  pages =    {7090--7101},
  year =     {2021},
  editor =   {Meila, Marina and Zhang, Tong},
  volume =   {139},
  series =   {Proceedings of Machine Learning Research},
  month =    {18--24 Jul},
  publisher =    {PMLR},
  pdf =      {http://proceedings.mlr.press/v139/lopez21a/lopez21a.pdf},
  url =      {http://proceedings.mlr.press/v139/lopez21a.html}
}

fedelopez77/sympa