Benchmark

This section presents the evaluation results of graph MaxCut algorithms under two settings: (1) distribution-wise, using the BA distribution; (2) instance-wise, using the Gset dataset.

1. Distribution-wise Benchmark

Table 1-1: Results for graph MaxCut on BA distribution

Nodes	Gurobi	S2V-DQN	S2V-DQN#Gurobi	ECO-DQN	ECO-DQN#Gurobi	Ours	Ours#Gurobi
100	283.7	272.3	-4.0%	283.63	-0.02%	283.7	0
200	583.3	557.2	-4.5%	581.7	-0.26%	582.2	-0.17%
300	880.4	825.4	-6.2%	873.9	-0.74%	878.0	-0.27%
400	1179.2	1100.6	-6.7%	1165.3	-1.18%	1174.2	-0.42%
500	1477.6	1374.9	-6.9%	1167.2	-1.0%	1471.4	-0.42%
600	1774.5	1647.2	-7.1%	1752.6	-1.2%	1769.1	-0.3%
700	2068.6	1907.3	-7.8%	2043.3	-1.2%	2062.6	-0.3%
800	2361.0	2182.1	-7.6%	2331.3	-1.3%	2358.7	-0.1%
900	2655.9	2425.5	-8.7%	2616.9	-1.5%	2647.0	-0.3%
1000	2952.2	2706.1	-8.3%	2911.9	-1.3%	2940.3	-0.4%

Note

The relative difference (columns with “#Gurobi”) represents the performance gap with Gurobi’s result. Higher values are better.

Table 1-2: Results for graph maxcut on ER distribution in distribution-wise scenario

#Nodes	dREINFORCE	Gurobi	dREINFORCE#Gurobi	S2V-DQN#Gurobi	dREINFORCE#S2V-DQN
100	507.83	507.83	0	-0.05% (100-200)	0.05%
200	1858.93	1856.13	0.151%	-1.05% (200 ~ 300)	1.20%
300	4063.20	4062.93	0	-2.65% (300 ~ 400)	2.66%
400	7042.10	7041.67	0	-3.59% (400 ~ 500)	3.60%
500	10862.30	10862.40	0	-5.77% (500 ~ 600)	5.77%
1000	41735.16	41765.87	-0.0735%	-5.07% (1000 ~ 1200)	5.00%
1100	50219.47	50286.8	-0.134%	-5.07% (1000 ~ 1200)	4.94%
1200	59506.30	59561.83	-0.093%	-5.07% (1000 ~ 1200)	4.98%
2000	163637.97	162162.30	0.91%	–	–
3000	363228.49	359632.17	1.00%	–	–

Table 1-3: Results for graph maxcut on powerlaw (PL) distribution

Nodes	Greedy	SDP	SA	GA	Gurobi	S2V-DQN (Pattern I)	PI-GNN (Pattern I)	ISCO (Pattern I)	dREINFORCE (Pattern II)	MCPG (Pattern II)	Jumanji (Pattern I)
100	268.2	270.6	268.4	282.9	282.9	278.5	271.3	282.8	282.9	282.9	282.9
200	548.0	554.4	550.5	578.0	578.7	563.1	572.5	578.3	578.7	578.7	578.7
300	824.6	833.9	826.4	877.2	877.2	859.4	843.2	876.1	879.5	878.2	879.5
400	1107.1	1117.8	1110.1	1173.2	1173.1	1152.7	1135.8	1169.6	1178.4	1173.9	1178.4
500	1386.6	1399.0	1391.5	1471.5	1468.1	1440.2	1455.3	1467.0	1475.6	1475.6	1460.4
600	1660.5	1683.4	1664.1	1768.3	1760.8	1725.6	1693.7	1758.5	1773.9	1770.1	1769.5
700	1950.8	1970.0	1955.0	2064.9	2056.7	2004.9	1982.4	2055.5	2061.2	2064.1	2058.6
800	2228.0	2260.7	2232.2	2361.4	2349.8	2302.4	2346.7	2353.4	2378.9	2375.4	2352.7
900	2507.0	2540.0	2514.1	2658.1	2643.9	2526.4	2594.3	2645.0	2676.1	2671.9	2667.4
1000	2784.3	2817.4	2792.7	2955.5	2942.1	2723.3	2903.4	2949.1	2980.2	2984.7	2963.9

2. Instance-wise Benchmark

Table 2-1: Results for graph MaxCut on the Gset dataset in instance-wise scenario

Graph	Nodes	Edges	BLS	DSDP	KHLWG	RUN-CSP	PI-GNN	iSCO	dREINFORCE	MCPG	Jumanji
G14	800	4694	3064	–	2922	3061	2943	3056	3064	3064	3064
G15	800	4661	3050	2938	3050	2928	2990	3046	3050	3050	2979
G22	2000	19990	13359	12960	13359	13028	13181	13289	13359	13359	13261
G49	3000	6000	6000	6000	6000	6000	5918	5940	6000	6000	5987
G50	3000	6000	5880	5880	5880	5880	5820	5874	5880	5880	5872
G55	5000	12468	10294	9960	10236	10116	10138	10218	10298	10296	10283
G70	10000	9999	9541	9456	9458	–	9421	9442	9586	9578	9554

Table 2-2: Results for TSP on the TSPLIB dataset in instance-wise scenario

Instance	LKH	S2V-DQN (Pattern I)	PI-GNN (Pattern I)	ISCO (Pattern I)	dREINFORCE (Pattern II)	MCPG (Pattern I)	Jumanji (Pattern II)	2-opt	Cheapest	Christofides
eil51	426	439	445	428	428	428	428	446	494	527
berlin52	7542	7542	7657	7542	7542	7542	7542	7788	9013	8822
st70	675	696	690	682	682	682	682	753	776	836
eil76	538	564	575	553	553	553	553	591	607	646
pr76	108159	108446	108536	108437	108405	108405	108405	115460	125935	137258
rat99	1211	1280	1291	1272	1260	1260	1260	1390	1473	1399
kroA100	21282	21897	21905	21886	21863	21863	21923	22876	24309	26578
kroB100	22141	22692	22783	22634	22607	22607	23107	23496	25582	25714
kroC100	20749	21074	21631	21014	21004	21004	21524	23445	25264	24582
kroD100	21294	22102	22304	22107	22019	22019	22087	23967	25204	27863
kroE100	22068	22913	22978	22869	22803	22803	23106	22800	25900	27452
rd100	7910	8159	8189	8153	8132	8114	8744	8757	8980	10002
eil101	629	659	669	702	651	651	664	702	693	728
lin105	14379	15023	15236	15014	14856	14907	15023	15536	16930	16568
pr107	44303	45113	45234	45013	44728	44765	45128	47058	52816	49192
pr124	59030	61623	61614	61514	61137	61185	63214	64765	65316	64591
bier127	118282	121576	122354	120367	120367	120139	121324	128103	141354	135134
ch130	6110	6270	6394	6231	6215	6238	6368	6470	7279	7367
pr136	96772	99474	99356	99136	98075	98013	104265	110531	109586	116069
ch144	58537	59436	59487	59415	59137	59137	602361	60321	73032	74684
pr150	6528	6985	6992	6834	6746	6784	7021	7232	7995	7641
kroA150	26524	27888	27956	27726	27162	27134	27195	29666	29963	32631
kroB150	26130	27209	28413	27135	27027	27109	27547	29517	31589	33260
pr152	73682	75283	77468	77368	74337	74337	75462	77206	88531	82118
u159	42080	45433	45624	44632	43501	43952	44367	47664	49898	48908
rat195	2323	2581	2674	2551	2529	2529	2631	2605	2806	2906
d198	15780	16453	16654	16231	16018	16237	16325	16596	17632	19002
kroA200	29368	30965	31632	30826	30537	30621	31848	32760	35340	37487
kroB200	29437	31692	31953	31321	31189	31024	31635	33107	35412	34490
tsp225	3916	4154	4161	4109	3967	4013	4150	4278	4470	4733
pr226	80369	81873	81962	81632	81031	80510	81310	89262	91023	98101
gil262	2378	2537	2561	2536	2487	2485	2607	2597	2800	2963
pr264	49135	52364	52961	52120	52018	52115	5326	54547	57602	55955
a280	2579	2867	2931	2861	2759	2768	2964	2914	3128	3125
pr299	48191	51895	52136	51134	50107	49357	51328	54914	58127	58660
lin318	42029	45375	45057	45653	44069	44068	45231	45263	49440	51484
linhp318	41345	45444	45647	44362	43246	43627	44367	45263	49440	51484

Table 2-3 Total flop count in tensor-train network of various sizes. The compared methods are OE Greedy, CTG Greedy, and CTG Kahypar.

Size	OE Greedy	CTG Greedy	CTG Kahypar	dREINFORCE (Pattern II)	MCPG (Pattern II)
N=100	30.927	30.705	30.710	30.404	30.404
N=200	61.030	60.808	60.810	60.507	60.507
N=400	121.236	121.014	121.010	120.713	120.968
N=600	181.442	181.220	181.220	180.919	180.976
N=800	241.648	241.426	241.430	241.125	241.125
N=1000	301.854	301.632	301.630	301.331	301.937
N=1500	–	–	452.150	451.846	451.925
N=2000	–	–	602.660	602.361	602.571

Table 2-4 Total flop count in Sycamore circuit of various cycles. The compared methods are OE Greedy, CTG Greedy, CTG Kahypar, AC-QDP, and RL-TNCO.

Cycles	OE Greedy	CTG Greedy	CTG Kahypar	AC-QDP	RL-TNCO	dREINFORCE (Pattern II)	MCPG (Pattern II)
m=12	17.795	17.065	13.407	13.037	10.736	10.117	10.117
m=14	19.679	19.281	14.149	13.851	12.869	12.029	12.726
m=16	25.889	23.152	17.013	17.061	–	13.967	14.532
m=18	26.793	23.569	17.681	17.412	–	17.113	17.113
m=20	26.981	25.622	18.825	18.823	18.543	18.158	18.17