Learning Combinatorial Optimization Algorithms over Graphs
https://papers.nips.cc/paper/7214-learning-combinatorial-optimization-algorithms-over-graphs.pdf
NeurIPS 2019でもしゃべていたのでついにちゃんと読んだ
はじめに
界隈はこの論文を最強だと思っているらしい。多分グラフ機械学習で離散最適化やっている界隈は全員これを知っている。これを倒せば知名度上がりそう
先行研究との差分
この論文が先行研究としているのはこれ。
まだ詳しく読んでいないが、policy gradientをtrainingに使っているらしく、それよりもDQNがいいよという流れで出てきたっぽい。 DQNはoff-policyで、experience replyができるため、policy gradientよりもsample efficientだと言っている。
トレーニング時にグラフのembeddingを更新していくのはこの研究の、先行研究に対する強みっぽい？（先行研究では最適解をembedしているらしい）
自分たちの手法との共通点・差分
共通点
action
actionは頂点のselection
reward
normalizeしていないのでまあ差分でもあるがMCTSしないので別にnormalizeしなくていい
差分
state, transition
stateの定義をグラフ、ではなく、actionで選んだ頂点の(ordered) sequenceとしている。グラフ自体は学習の中で不変。自分たちの手法だと、(少なくともMISについては)グラフをだんだん小さくしていたが、この手法だと最後に選んだ頂点に新しくラベルをつけていく遷移をするだけ。
Q-Learning
そんなに異常Q-Learningをしていなかった。
アルゴリズム中のBatchサイズやは解く問題によってかなり調整しているっぽい。
embedding
GNNよりも一般的なフレームワークに見える。4-hopしか見ていないのでかなり浅い。パラメータはたくさんある。自分たちのGNNだと1-dimensionalなembeddingをしていたような気がするが、とくにweightedグラフに弱すぎるし次元を増やした方がいい気がする。こちらの論文では64次元
グラフも前処理としてkNNをとっている。
感想
自分で実装し直したほうがいい気がする。仮に精度出なかったら工夫したであろうところにきづけるだろうし
