Implementation of our NeurIPS 2021 paper "A Bi-Level Framework for Learning to Solve Combinatorial Optimization on Graphs".

Overview

PPO-BiHyb

This is the official implementation of our NeurIPS 2021 paper "A Bi-Level Framework for Learning to Solve Combinatorial Optimization on Graphs".

A Brief introduction

In this paper, we propose a general deep learning pipeline for combinatorial optimization problems on graphs. The neural network is learned with Proximal Policy Optimization (PPO), under our Bi-Level Hybrid optimization pipeline. Thus our method is called PPO-BiHyb. This section is aimed for a brief summary, and we recommend referring to our paper if you do not want to miss any details.

The family of existing machine learning for combinatorial optimization methods follow the following single-level pipeline: single-level optimization and the neural network is designed to lean the mapping from the input graph G to the decision variable X. It brings challenges like the sparse reward issue in RL training, and it also makes the model design non-trivial to ensure that it has enough model capacity to learn such a mapping.

In contrast, in this paper, we propose a bi-level optimization formulation: bi-level optimization where we introduce the optimized graph G'. The upper-level problem is to optimize G', and we design a PPO-based agent for this task; the lower-level optimization is to solve the optimization problem with G', and we resort to existing heuristic algorithms for this task.

The overview of our pipeline is summarized as follows overview

And Here is our implementation of the proposed framework on 3 problems: implement-on-3-problems

  • DAG scheduling problem models the computer resource scheduling problem in data centers, where the computer jobs are represented by Directed Acyclic Graphs (DAGs) and our aim is to minimize the makespan time to finish all jobs as soon as possible. This optimization problem is NP-hard.
  • Graph Edit Distance (GED) problem is a popular graph distance metric, and it is inherently an NP-hard combinatorial optimization problem whose aim is to minimize the graph edit cost between two graphs.
  • Hamiltonian Cycle Problem (HCP) arises from the famous 7 bridges problem by Euler: given a graph, decide whether exist a valid Hamiltonian cycle in this graph (i.e. a path that travels all nodes without visiting a node twice). This decision problem is NP-complete.

Experiment Results

DAG scheduling (objective & relative: smaller is better)

TPC-H-50 (#nodes=467.2) TPC-H-100 (#nodes=929.8) TPC-H-150 (#nodes=1384.5)
objective relative objective relative objective relative
shortest job first 12818 30.5% 19503 15.3% 27409 12.2%
tetris scheduling 12113 23.3% 18291 8.1% 25325 3.7%
critical path 9821 0.0% 16914 0.0% 24429 0.0%
PPO-Single 10578 7.7% 17282 2.2% 24822 1.6%
Random-BiHyb 9270 -5.6% 15580 -7.9% 22930 -6.1%
PPO-BiHyb (ours) 8906 -9.3% 15193 -10.2% 22371 -8.4%

GED (objective & relative: smaller is better)

AIDS-20/30 (#nodes=22.6) AIDS-30/50 (#nodes=37.9) AIDS-50+ (#nodes=59.6)
objective relative objective relative objective relative
Hungarian 72.9 94.9% 153.4 117.9% 225.6 121.4%
RRWM 72.1 92.8% 139.8 98.6% 214.6 110.6%
Hungarian-Search 44.6 19.3% 103.9 47.6% 143.8 41.1%
IPFP 37.4 0.0% 70.4 0.0% 101.9 0.0%
PPO-Single 56.5 51.1% 110.0 56.3% 183.9 80.5%
Random-BiHyb 33.1 -11.5% 66.0 -6.3% 82.4 -19.1%
PPO-BiHyb (ours) 29.1 -22.2% 61.1 -13.2% 77.0 -24.4%

HCP (TSP objective: smaller is better, found cycles: larger is better)

FHCP-500/600 (#nodes=535.1)
TSP objective found cycles
Nearest Neighbor 79.6 0%
Farthest Insertion 133.0 0%
LKH3-fast 13.8 0%
LKH3-accu 6.3 20%
PPO-Single 9.5 0%
Random-BiHyb 10.0 0%
PPO-BiHyb (ours) 6.7 25%

Environment set up

This code is developed and tested on Ubuntu 16.04 with Python 3.6.9, Pytorch 1.7.1, CUDA 10.1.

Install required pacakges:

export TORCH=1.7.0
export CUDA=cu101
pip install torch==1.7.1+${CUDA} torchvision==0.8.2+${CUDA} torchaudio===0.7.2 -f https://download.pytorch.org/whl/torch_stable.html
pip install --no-index --upgrade torch-scatter -f https://pytorch-geometric.com/whl/torch-${TORCH}+${CUDA}.html
pip install --no-index --upgrade torch-sparse -f https://pytorch-geometric.com/whl/torch-${TORCH}+${CUDA}.html
pip install --no-index --upgrade torch-spline-conv -f https://pytorch-geometric.com/whl/torch-${TORCH}+${CUDA}.html
pip install --upgrade torch-geometric
pip install tensorboard
pip install networkx==2.2
pip install ortools
pip install texttable
pip install tsplib95
pip install cython

Install SVN which is required when retriving the GED dataset:

sudo apt install subversion

Compile the A-star code which is required by the GED problem:

python3 setup.py build_ext --inplace

Install LKH-3 which is required by the HCP experiment:

wget http://webhotel4.ruc.dk/~keld/research/LKH-3/LKH-3.0.6.tgz
tar xvfz LKH-3.0.6.tgz
cd LKH-3.0.6
make

And you should find an executable at ./LKH-3.0.6/LKH, which will be called by our code.

Run Experiments

We provide the implementation of PPO-BiHyb and the single-level RL baseline PPO-Single used in our paper. To run evaluation from a pretrained model, replace train by eval in the following commands.

DAG Scheduling

PPO-BiHyb:

python dag_ppo_bihyb_train.py --config ppo_bihyb_dag.yaml

PPO-Single:

python dag_ppo_single_train.py --config ppo_single_dag.yaml

To test different problem sizes, please modify this entry in the yaml file: num_init_dags: 50 (to reproduce the results in our paper, please set 50/100/150)

Graph Edit Distance (GED)

PPO-BiHyb:

python ged_ppo_bihyb_train.py --config ppo_bihyb_ged.yaml

PPO-Single:

python ged_ppo_single_train.py --config ppo_single_ged.yaml

To test different problem sizes, please modify this entry in the yaml file: dataset: AIDS-20-30 (to reproduce the results in our paper, please set AIDS-20-30/AIDS-30-50/AIDS-50-100)

Hamiltonian Cycle Problem (HCP)

PPO-BiHyb:

python hcp_ppo_bihyb_train.py --config ppo_bihyb_hcp.yaml

PPO-Single:

python hcp_ppo_single_train.py --config ppo_single_hcp.yaml

Some Remarks

The yaml configs are set for the smallest sized problems by default. For PPO-Single, you may need to adjust the max_timesteps config for larger-sized problems to ensures that the RL agent can predict a valid solution.

Pretrained models

We provide pretrained models for PPO-BiHyb on these three problems, which are stored in ./pretrained. To use your own parameters, please set the test_model_weight configuration in the yaml file.

Citation and Credits

If you find our paper/code useful in your research, please citing

@inproceedings{wang2021bilevel,
    title={A Bi-Level Framework for Learning to Solve Combinatorial Optimization on Graphs}, 
    author={Runzhong Wang and Zhigang Hua and Gan Liu and Jiayi Zhang and Junchi Yan and Feng Qi and Shuang Yang and Jun Zhou and Xiaokang Yang},
    year={2021},
    booktitle={NeurIPS}
}

And we would like to give credits to the following online resources and thank their great work:

Owner
[email protected]
Thinklab at Shanghai Jiao Tong University, led by Prof. Junchi Yan.
<a href=[email protected]">
The Body Part Regression (BPR) model translates the anatomy in a radiologic volume into a machine-interpretable form.

Copyright © German Cancer Research Center (DKFZ), Division of Medical Image Computing (MIC). Please make sure that your usage of this code is in compl

MIC-DKFZ 40 Dec 18, 2022
This is the source code for our ICLR2021 paper: Adaptive Universal Generalized PageRank Graph Neural Network.

GPRGNN This is the source code for our ICLR2021 paper: Adaptive Universal Generalized PageRank Graph Neural Network. Hidden state feature extraction i

Jianhao 92 Jan 03, 2023
Deep Q Learning with OpenAI Gym and Pokemon Showdown

pokemon-deep-learning An openAI gym project for pokemon involving deep q learning. Made by myself, Sam Little, and Layton Webber. This code captures g

2 Dec 22, 2021
This is a repository with the code for the ACL 2019 paper

The Story of Heads This is the official repo for the following papers: (ACL 2019) Analyzing Multi-Head Self-Attention: Specialized Heads Do the Heavy

231 Nov 15, 2022
The original implementation of TNDM used in the NeurIPS 2021 paper (no longer being updated)

TNDM - Targeted Neural Dynamical Modeling Note: This code is no longer being updated. The official re-implementation can be found at: https://github.c

1 Jul 21, 2022
Doing the asl sign language classification on static images using graph neural networks.

SignLangGNN When GNNs 💜 MediaPipe. This is a starter project where I tried to implement some traditional image classification problem i.e. the ASL si

10 Nov 09, 2022
A Pytorch Implementation of a continuously rate adjustable learned image compression framework.

GainedVAE A Pytorch Implementation of a continuously rate adjustable learned image compression framework, Gained Variational Autoencoder(GainedVAE). N

39 Dec 24, 2022
Code accompanying "Dynamic Neural Relational Inference" from CVPR 2020

Code accompanying "Dynamic Neural Relational Inference" This codebase accompanies the paper "Dynamic Neural Relational Inference" from CVPR 2020. This

Colin Graber 48 Dec 23, 2022
计算机视觉中用到的注意力模块和其他即插即用模块PyTorch Implementation Collection of Attention Module and Plug&Play Module

PyTorch实现多种计算机视觉中网络设计中用到的Attention机制,还收集了一些即插即用模块。由于能力有限精力有限,可能很多模块并没有包括进来,有任何的建议或者改进,可以提交issue或者进行PR。

PJDong 599 Dec 23, 2022
The FIRST GANs-based omics-to-omics translation framework

OmiTrans Please also have a look at our multi-omics multi-task DL freamwork 👀 : OmiEmbed The FIRST GANs-based omics-to-omics translation framework Xi

Xiaoyu Zhang 6 Dec 14, 2022
A best practice for tensorflow project template architecture.

A best practice for tensorflow project template architecture.

Mahmoud Gamal Salem 3.6k Dec 22, 2022
RLDS stands for Reinforcement Learning Datasets

RLDS RLDS stands for Reinforcement Learning Datasets and it is an ecosystem of tools to store, retrieve and manipulate episodic data in the context of

Google Research 135 Jan 01, 2023
SoGCN: Second-Order Graph Convolutional Networks

SoGCN: Second-Order Graph Convolutional Networks This is the authors' implementation of paper "SoGCN: Second-Order Graph Convolutional Networks" in Py

Yuehao 7 Aug 16, 2022
MQBench: Towards Reproducible and Deployable Model Quantization Benchmark

MQBench: Towards Reproducible and Deployable Model Quantization Benchmark We propose a benchmark to evaluate different quantization algorithms on vari

494 Dec 29, 2022
Source code of the paper "Deep Learning of Latent Variable Models for Industrial Process Monitoring".

Source code of the paper "Deep Learning of Latent Variable Models for Industrial Process Monitoring".

Xiangyin Kong 7 Nov 08, 2022
Multi-Output Gaussian Process Toolkit

Multi-Output Gaussian Process Toolkit Paper - API Documentation - Tutorials & Examples The Multi-Output Gaussian Process Toolkit is a Python toolkit f

GAMES 113 Nov 25, 2022
Hybrid Neural Fusion for Full-frame Video Stabilization

FuSta: Hybrid Neural Fusion for Full-frame Video Stabilization Project Page | Video | Paper | Google Colab Setup Setup environment for [Yu and Ramamoo

Yu-Lun Liu 430 Jan 04, 2023
Some bravo or inspiring research works on the topic of curriculum learning.

Towards Scalable Unpaired Virtual Try-On via Patch-Routed Spatially-Adaptive GAN Official code for NeurIPS 2021 paper "Towards Scalable Unpaired Virtu

131 Jan 07, 2023
Offline Multi-Agent Reinforcement Learning Implementations: Solving Overcooked Game with Data-Driven Method

Overcooked-AI We suppose to apply traditional offline reinforcement learning technique to multi-agent algorithm. In this repository, we implemented be

Baek In-Chang 14 Sep 16, 2022
Structure-Preserving Deraining with Residue Channel Prior Guidance (ICCV2021)

SPDNet Structure-Preserving Deraining with Residue Channel Prior Guidance (ICCV2021) Requirements Linux Platform NVIDIA GPU + CUDA CuDNN PyTorch == 0.

41 Dec 12, 2022