C#/.net>> treewidth-prediction>> 返回
项目作者： pfnet-research

项目描述 ：
Prediction of Treewidth using Graph Neural Network, developed as part of PFN summer internship 2019.
高级语言： Jupyter Notebook
项目地址: git://github.com/pfnet-research/treewidth-prediction.git
创建时间： 2019-10-10T01:08:20Z
项目社区：https://github.com/pfnet-research/treewidth-prediction
开源协议：MIT License
下载


Prediction of Treewidth using Graph Neural Network

This code predicts the treewidth by using graph neural network.
If you want more information about this code, please read my article “Graph Neural Network を用いたグラフの木幅予測” (sorry, written in Japanese) on Preferred Networks Research Blog.

This code also implements a general framework of GNN described in [1].
In detail, this code implements max, average and sum aggregations and readouts described the paper and is compatible with GPU.
We also provide the trained model and random graph datasets.

This software is developed as part of PFN summer internship 2019 and the main developer is Yuta Nakano.

Outline of prediction flow

This code follows the prediction flow described below.

  1. Training GNN in classification task or regression task.
  2. Predicting the treewidth of a given graph by using trained GNN model.

Details are written in above-mentioned article.

Dependencies

This code has been tested over Chainer 6.3.0 and python 3.7.4.
If you haven’t installed chainer, please install chainer following the instructions on the official website.
If you want to run on GPU, please install CuPy following the instructions on the official website.

Here is other dependencies.

  • matplotlib
  • networkx
  • numpy
  • scikit-learn
  • scipy
  • seaborn
  • timeout-decorator

You can install these dependencies by requirements.txt. Please run the below script.

  1. pip install -r requirements.txt

Example

Training GNN (You can skip this)

Note: We provide pretrained model, so you can use this model and skip this step.

First, unzip the dataset file by running the below script.

  1. ./unpack.sh

Approach 1

Run the below script.

  1. python GNN.py --task_type Task1

Default parameters are not the best performing hyper-parameters.
So you may want to tune hyper-parameters.
To check hyper-parameters to be specified, please type below.

  1. python GNN.py --help

Approach 2

Run the below script.

  1. python GNN.py --task_type Regression

Predicting Treewidth

Approach 1

Run the below script.

  1. python main.py --task_type approach1

Approach 2

Run the below script.

  1. python main.py --task_type approach2

License

MIT License. We provide no warranty or support for this implementation. Use it at your own risk.

Please see the LICENSE file for details.

Reference

  1. Keyulu Xu, Weihua Hu, Jure Leskovec, Stefanie Jegelka. How Powerful are Graph Neural Networks?, ICLR 2019. arXiv
  2. PACE-challenge/Treewidth: List of Treewidth solvers, instances, and tools, https://github.com/PACE-challenge/Treewidth