Run algorithms

Commands:

python greedy.py           #Local Search
python random_walk.py
python simulated_annealing.py

Datasets

Take g14.txt (an undirected graph with 800 nodes and 4694 edges) as an example:

800 4694 # #nodes is 800, and #edges is 4694.

1 7 1 # node 1 connects with node 7, weight = 1

1 10 1 # node 1 connects node 10, weight = 1

1 12 1 # node 1 connects node 12, weight = 1

Results

Results will be written to a file xxx.txt in the folder "result". The first column is nodes, and the second column is label.

1 2 # node 1 in set 2

2 1 # node 2 in set 1

3 2 # node 3 in set 2

4 1 # node 4 in set 1

5 2 # node 5 in set 2

Performance

In the following experiments, we used GPU during training by default. The best-known results are labed in bold.

The results are stored in the folder "result". Take Gset as an example.

Gset was created by Stanford University.

graph	#nodes	#edges	BLS	DSDP	KHLWG	RUN-CSP	PI-GNN	Gurobi (0.5 h)	Gurobi (1 h)	Gap	Ours	Improvement
G14	800	4694	3064		2922	3061	2943	3034	3042	3.61%	3064	+0%
G15	800	4661	3050	2938	3050	2928	2990	3016	3033	3.33%	3050	+0%
G22	2000	19990	13359	12960	13359	13028	13181	13062	13129	28.94%	13359	+0%
G49	3000	6000	6000	6000	6000	6000	5918	6000	6000	0	6000	+0%
G50	3000	6000	5880	5880	5880	5880	5820	5880	5880	0	5880	+0%
G55	5000	12468	10294	9960	10236	10116	10138	10103	10103	11.92%	10298	+0.04%
G70	10000	9999	9541	9456	9458	-	9421	9489	9490	2.26%	9583	+0.44%

L2A's results are represented as strings. How to transfer the strings into binary results?

Take data/syn/powerlaw_100_ID0.txt as an example, the result is "4SuqhIaQimYjyk_sX" by L2A, which can be transferred to a binary vector by calling the function str_to_bool in EncoderBase64 in evaluator.py.