Approximation Ratios of Graph Neural Networks for Combinatorial Problems
読んだ。以下メモ
結局何したん？
- GNN って Distributed Local Algorithm と関連してるよね
- なので、Distributed Local Algorithm の理論使って GNN がどれくらいの近似解を算出できるかを解析したよ
- んで、理論的に一番な GNN である CPNGNN を提案したよ
- Distributed Local Algorithm は GNN の Aggregation っぽいことを行ってグラフ上の組合せ最適化を解くアルゴリズム
- なので、Distributed Local Algorithm と GNN で解ける問題クラスが同じだよってことを示して解析してる
- 今回 Input Graph の最大次数を Δ で固定する仮定を置いて解析してる（よくある仮定らしい）
じゃあ、今回の GNN の売りポイントって何っていうと
- Message Passing において、ノードごとに渡すメッセージを変えている
- Aggregate した後の各要素を Concatenate する（普通 sum とか max とか ave とっちゃう）
ってところ。でも2つ目は最大次数の仮定がないとできないよね……
ノードごとに渡すメッセージを変える部分は Port numbering と呼ばれるテクニックを用いているらしい。
で、finding single leaf problem って問題に対して適用してみたら GCN とかじゃ溶けなかったけど CPNGNN だとできたよ。
コメント
- 実際に学習してみたらどうなったんだろう…… Empirical な解析がなかった
- 結構最大次数を Bound する仮定が効いてそう……とは思いました
