search

Hanjun-Dai / graph_comb_opt

Implementation of "Learning Combinatorial Optimization Algorithms over Graphs"
https://arxiv.org/abs/1704.01665
MIT License
491 stars 135 forks source link

Questions about understanding s2v_mvc #15

Closed sungsoo-ahn closed 5 years ago

sungsoo-ahn commented 5 years ago

Hi, thanks for the great paper and sharing your code!

I really liked your paper and currently trying to re-implement it in pytorch / deep graph library (https://www.dgl.ai/). I would be grateful if you could help me out with some of my questions regarding the code (specifically s2v_mvc).

For the n-step q net fitting in s2v_mvc folder,

  1. it says n=5 for minimum vertex cover in the paper and "evaluate.sh", but the code "run_nstep_dqn.sh" use n=2 for training. Would I be able to obtain the results in the Figure D.2 in the appendix of the paper, if I switch to n=5 without changing other hyper-parameters?

For the implementation of q net, I am trying to understand the differences between the code and the paper (which I am totally happy with). Could you confirm my following understandings?

  1. The implemented q_net takes input as an "uncovered" subgraph with respect to the currently selected nodes with node features=1.
  2. The network takes an additional 3-dimensional input "aux_feat" containing a) ratio of covered nodes, b) ratio of covered edges and c) a bias term.

It would also be more than helpful if you could point out other "mvc-specific" implementation of the code. Thanks very much in advance!

Hanjun-Dai commented 5 years ago

Hi,

Thanks for your interest in our work, and sorry for the possible confusion.

  1. I tried with n=1~5, and generally they should give similar results but you can try with n=2 first. Generally if the graph is large then I may slightly increase n.

  2. Yes we are working on the 'residual graph' which only contains the uncovered nodes, that's why the node features are useless in this case, since all the nodes are uncovered, and I simply set them to ones.

  3. Yes you are right, those additional features are part of the state representation.

I think generally the above tricks are 'mvc-specific'. Other minor points are: 1) The graph neural network architecture might differ a bit than other problem instances, but again, this should be minor and shouldn't affect the performance much. If you use other more recent GNNs that might even be better. 2) when dealing with larger graphs, I first initialize the model with parameters trained on small graphs -- and this trick is general, not only mvc-specific.

Let me know if you have further questions.

sungsoo-ahn commented 5 years ago

Thanks very much! It is working well now.

seokhyunan commented 1 year ago

@Hanjun-Dai Are MVC, SCP the only case in your implementation that only embeds the residual graph?

(Except for MVC and SCP, your code seems to embed the entire graph, not the residual graph, as described in the paper. I would like to ask if my understanding of your code is correct.)

On the other hand, when our group implemented it again with PyTorch, we confirmed that the results were reproduced even if we embed only the residual graph in order to select the next node in other problems.

Thank you so much for your code and paper.

Hanjun-Dai commented 1 year ago

Hi, for other cases the 'residual' graph may still be the original graph. Generally the 'residual graph' refers to the minimal graph that is necessary for rl agent to make further actions.