Mwc

This repository contains the c++ source codes of the machine learning model for problem reduction to solve maximum weight clique problems.

Install & compile:

packages required: 1) cmake-2.8.4 or above; and 2) gcc-7.3.0 or above install: 'git clone https://github.com/yuansuny/mwc.git' compile: 1) move to the directory: 'cd mwc' 2) create a build directory: 'mkdir build' 3) move to the build directory: 'cd build' 4) run cmake: 'cmake ..' 5) run makefile: 'make'

Usage:

Usage: ./MWC [options] datafile options: -m : set problem reduction method (default 3) 0 -- no problem reduction 1 -- correlation-based measure 2 -- ranking-based measure 3 -- kernel SVM, dual (training and testing are slow) 4 -- linear SVM, primal (training and testing are fast) -n : set whether training is required (default 0) 0 -- training is not required; using ML model already trained 1 -- training is required; train a ML model to use; the training graphs can be specified in the src/main.cpp file; the optimal solutions for the training graphs are required. -k : set kernel type for kernel SVM (default 2) 0 -- linear: u'v 1 -- polynomial: (gammau'v + coef0)^degree 2 -- radial basis function: exp(-gamma|u-v|^2) 3 -- sigmoid: tanh(gamma*u'v + coef0) -s : set solution method to solve the reduce problem (default 0) 0 -- TSM 1 -- WLMC 2 -- LSCC 3 -- FastWCLQ -t : set the cutoff time in seconds (default 1000 seconds) -c : set the threshold for correlation-based measure (default 0.0) -r : set the threshold for ranking-based measure (default 0.01) -a : set the penalty for miss-classifying positive data for SVM anum0/num1 (default 10)

Examples:

./MWC p_hat1000-2 : solve the graph p_hat1000-2.wclq using default parameter setting (kernel SVM, TSM etc). ./MWC -m 0 -s 2 p_hat1000-2 : solve the original graph p_hat1000-2.wclq using LSCC without problem reduction. ./MWC -m 4 -s 1 p_hat1000-2 : solve the graph p_hat1000-2.wclq using WLMC with the linear SVM as preprocessing method. ./MWC -m 1 -c 0.01 -t 100 p_hat1000-2 : solve the graph p_hat1000-2.wclq using TSM (default) and the correlation-based measure (threashold 0.01) as preprocessing method; cutoff time set to 100 seconds. ./MWC -m 3 -n 1 -k 1 -a 100 p_hat1000-2 : train a SVM model with polynomial kernel and penalty a=100 to solve the graph p_hat1000-2.wclq; you can specify the training graphs in the src/main.cpp file.

References:

Sun Y, Li X, Ernst A. Using Statistical Measures and Machine Learning for Graph Reduction to Solve Maximum Weight Clique Problems. IEEE Transactions on Pattern Analysis and Machine Intelligence, accepted in Nov 2019. (https://ieeexplore.ieee.org/document/8908752)

License:

This program is to be used under the terms of the GNU General Public License (http://www.gnu.org/copyleft/gpl.html). Author: Yuan Sun, Xiaodong Li & Andreas Ernst e-mail: yuan.sun@rmit.edu.au, xiaodong.li@rmit.edu.au, andreas.ernst@monash.edu Copyright notice: (c) 2019 Yuan Sun, Xiaodong Li & Andreas Ernst