Combinatorial Optimization with Graph Convolutional Networks and Guided Tree Search
読んだ。
NeurIPS 2018に通ってる。Intel LabとHKUSTの人だった（見たことない）（サーベイ力無し）
以下雑まとめ
- 例にもれず組合せ最適化×GNNのお話
- 着目してる問題は、Maximum Independent SetとMinimum Vertex CoverとMaximal CliqueとSAT
- MIS以外の問題は、全部MISに落とし込めるのでMISだけを考える
- GNNを使う理由としては、頂点が解に含まれる確率を予測して、探索木を展開していく際にうまく使いたいというモチベがあるから
- まあこれはよしなにGNNを構成すれば可能（今回はGCN使ってる）
- でも、4頂点のサイクルグラフ（あってる？）を考えると、２パターンのMIS解ある、こんな感じで１つのグラフにいろいろな解があるし、各頂点が常に全ての解に含まれるかといったらそうではない
- 多様性を考慮しないとアカン、つらい…… ならM個の解それぞれに各頂点が含まれる確率を生成するようにすればよくね？ これは、いい感じにLoss関数とかを書き換えると可能になる
- で、他のLocal SearchとかGraph Reductionテクを使った上で、この頂点が解に含まれるかベクトルをM個生成、これを使って確率が高い方からGreedyに使って行き、M個の解を生成
- その中でいいのを取るというかんじ
- 生成速度も早くて、生成される解の品質もSoTAなMIS Solverと変わらなくてよかった（完）
以下雑感
- これめちゃくちゃ頭いい、プロか？（プロだが）
- というかGCNの部分を他のモデルに変えるだけでも十分性能上がりそう〜〜〜
- でもなんでMISに落とし込んでるんだろう？ 単純にMVCでもMCでもいけるじゃん？（Graph ReductionとかLocal Searchとか使いたいから？）（それは似たようなものがあるじゃん？）
- MISは実質Polyタイム（よしなにBranch Ruleを定めると実測値めちゃはやらしい）とか言われてるくらいだし、他の分野で競うのが良さそうなのになぁ……
- Message Passingでうまく抽出できる構造って、密な部分構造（クリークっぽいの）だと思うんだけどどうなんだろ？
- だからMaximal Cliqueはいい感じの結果でそうなんだけど、筆者は検証してない？なんで？（悪いから？）
- あと、学習にかかったのが16時間くらいで思ったより短かった（そんなもん？）
近いうち木幅のまともな記事を書きます（）
