search

Stalence / erdos_neu

Official Repo for the NeurIPS2020 paper "Erdos Goes Neural: An Unsupervised Learning Framework for Combinatorial Optimization on Graphs"
43 stars 11 forks source link

Could you please provide the code for the baseline methods? #5

Closed bokveizen closed 2 years ago

bokveizen commented 2 years ago

Thank you for this wonderful work. The detailed descriptions of several baseline methods cannot be found in the paper, nor in the code here. Could you please provide the code or detailed explanation for the baseline methods?

Stalence commented 2 years ago

Hello,

All the baselines that are used are cited and have their own corresponding public repositories. You may find the links for the repos in the papers or with a quick google search. Is there a specific baseline that you need help with? If you can explain to me what you are looking for I might be able to help.

bokveizen commented 2 years ago

Thank you for your reply. May I know where I can find the detailed algorithms or implementations of Bomze/MS/L1/L2 GNN? The cited papers were published in the last century and I could not find any repos for them.

Stalence commented 2 years ago

I see. Since those are mostly used as "ablations" than full-fledged baselines I did not explicitly write down all the formulas and just cited the papers that use them. But you are right, it's better if I make this more self-contained so I will update the supplementary material with more information. I'll get the code as well soon.

Until that's taken care of, here's most of the important info in condensed form.

As we explain in the paper, Bomze/MS has the same setup as Erdos. The key difference is the loss function and the discretization. As a shortcut, you can find both mathematical expressions for Bomze and Motzkin Strauss (MS) here: https://link.springer.com/chapter/10.1007/978-1-4757-3023-4_1. Just go to page 9, equations 9 and 11 for MS and Bomze respectively. Swap the Erdos expression with the terms of equations 9 and 11 in the loss (make sure you get the sign correctly). For discretization and the experimental protocol (# of runs, etc.) you can find the details in our paper.

Similarly, for L1 and L2, consider the paper that is cited https://arxiv.org/abs/1306.1185. L1 uses the formula in equation 3 to relax the cut (i.e., the graph total variation), while L2 takes equation 3 and instead of an absolute value uses the square of the pairwise differences (that's the Laplacian quadratic form).

bokveizen commented 2 years ago

Thanks a lot for your reply!