Deep Generative Models of Graphs②（Section2以降）｜Graph Neural Networkの研究を追う #2
#1では連載の経緯を記載し、下記の論文のAbstractとIntroductionを確認し、概要を把握しました。
[1803.03324] Learning Deep Generative Models of Graphs
#2ではSection2のRelated Work以降の主要な内容についてご紹介します。
以下目次になります。
1. Related Work(Section2)
2. The Sequential Graph Generation Process(Section3)
3. Learning Graph Generative Models(Section4)
4. Experiments(Section5)
5. Discussions and Future Directions＆Conclusion(Section6〜7)
6. まとめ
1. Related Work(Section2)
1節ではSection2のRelated Workの内容を取り扱います。
第一パラグラフでは、最も以前からあるグラフの確率モデルとして、ErdosとRenyiのエッジの独立同分布の取り扱い(assume)が紹介されています。以降の研究も紹介されており、WattsとStrogatzの"the small-world model[1998]"がこの中だと有名ではないかと思います。
第三パラグラフではこのDGMGの研究のグラフ生成モデル(graph generative model)を構築するにあたって参考にした"graph nets"について紹介しています。"graph nets"のオリジナルとしてScarselliの研究[2009]を紹介しており、2015〜2017の先行研究も紹介しています(確認しているDGMGは2018年)。DGMGの研究では"graph nets"の考え方をグラフ生成の過程における様々な選択を行うにあたっての表現学習に用いたとされています。
第四パラグラフでは類似の先行研究としてJohnsonの研究[2017]を参照しています。ちょっと文面だけだと読み取りづらいので類似の研究で挙げていることだけ把握し、ここでは流したいと思います。
2. The Sequential Graph Generation Process(Section3)
2節ではSection3のThe Sequential Graph Generation Processの内容を取り扱います。
まず、第一パラグラフではDGMGにおけるグラフの生成モデルは連続的な過程(sequential process)で生成を行うとしています。sequential processは、『一度に1つのノードを作成し、既存の部分グラフ(partial graph)のノードとの連結を1つずつ考える流れ』として説明されています。
第二パラグラフでは、グラフ生成における具体的な流れについて、図やアルゴリズムとともにステップが言及されています。(1)ノードを生成するか生成を打ち切るか(terminate)をサンプリングする、(2)ノードをグラフに追加する、(3)新しいノードと既存のグラフのノード間にエッジを追加するか確認する、(4)エッジを追加する、の4つのステップが明示されています。(3)では既存のグラフのノード全てに対して確認を行い、エッジの追加が終わったら(1)に戻るとされています。
処理プロセスの図やアルゴリズムについては上記のように記載されています。実装したり実装を確認したりする際はアルゴリズムも参考にすると良さそうです。
第三パラグラフでは、生成のプロセス(generation process)の微調整(tweak)の例を紹介しています。有向グラフなのか無向グラフなのかや、自身へのエッジ(self-loop)や2つのノード間に複数のエッジの付加(multiple edges)を禁止したりするなどの構造的制約を設けることなどを具体例として挙げられています。
第四パラグラフでは第二パラグラフと同様にグラフの生成にあたってのプロセスの記載を行っています。
一つのグラフが異なる過程で生成される例として、Figure8を参照しています。左と右で生成の手順は違いますが、結果的に同じグラフが生成されていることが確認できるかと思います。
第五パラグラフでは、DGMGのグラフ生成過程の応用事例としてLSTMを用いた言語モデル(LSTM language models)について紹介しています。
3. Learning Graph Generative Models(Section4)
3節ではSection4の"Learning Graph Generative Models"について取り扱います。
生成モデルの構成については基本的には上記の数式をベースに理解すると良いと思います。(7)や(8)の数式でノードやエッジの追加を判断しています。学習にあたってはSection4-2でモンテカルロ法をベースにしたサンプリングを用いた手法について記載されています。
4. Experiments(Section5)
5. Discussions and Future Directions＆Conclusion(Section6〜7)
今回は省略します。
6. まとめ
#1と#2でDGMGについて確認を行いました。
#3以降でも引き続き関連の論文について参照していければと思います。
