MATA*

This repository is the implementation of MATA*, which presents a data-driven hybrid approach MATA* based on Graph Neural Networks (SEGCN) and A* algorithms, which leverage the learned candidate matching nodes to prune un-promising search directions of A*LSa algorithm to approximate GED.

Get Started

Install Requirements

conda create -n envmata python=3.8.13
source activate envmata
  
conda install pytorch==1.9.0 torchvision==0.10.0 torchaudio==0.9.0 cpuonly -c pytorch 
pip install torch-cluster==1.5.9 -f   https://pytorch-geometric.com/whl/torch-1.9.0+cpu.html
pip install torch-scatter==2.0.9 -f   https://pytorch-geometric.com/whl/torch-1.9.0+cpu.html
pip install torch-sparse==0.6.12 -f  https://pytorch-geometric.com/whl/torch-1.9.0+cpu.html
pip install torch-spline-conv==1.2.1 -f  https://pytorch-geometric.com/whl/torch-1.9.0+cpu.html
pip install torch-geometric==2.0.4
pip install -r requirements_test.txt

Note that：

1. The given Pytorch 1.9 is support by CPU. For different CUDA versions of Pytorch, please refer to the official installation guide for more details.
2. You may change the version of networkx to 1.10 for running A*Beam, Hungarian, and VJ, follow the instructions on https://github.com/yunshengb/graph-matching-toolkit

Build C extension

The A*LSa algorithm is implemented by C based on the official repository https://github.com/LijunChang/Graph_Edit_Distance. Follow these instructions to build the C code:

g++ -shared -Wl,-soname,mata -o mata.so -fPIC Mata.cpp Application.cpp

Then the file mata.so is generated in the path /Astar/. For the using of c++11, you need append -std=c++11 in this command.

Running Test

1. Test the results on AIDS datasets

   python main.py --dataset AIDS700nef --max-degree 12 --topk 4 --batch-size 128 --epochs 10000  --task 3 --test > test_aids.txt 
   

2. IMDB

   python main.py  --dataset IMDBMulti --max-degree 40  --topk 6 --batch-size 128 --epochs 10000  --val-epochs 1000 --task 3 --test 
   

3. CANCER

   python main.py  --dataset CANCER --max-degree 18 --topk 3 --batch-size 128 --epochs 6000  --val-epochs 800 --task 3 --test
   

Note that: The ground-truth of IMDB and CANCER are generated by the smallest edit distances of A*Beam, Hungarian, and VJ. The best results should be re-computed when evaluating IMDB and CANCER.