Re:ゼロから始めるML生活

どちらかといえばエミリア派です

【論文メモ:GraphGAN】GraphGAN: Graph Representation Learning with Generative Adversarial Nets

論文

[1711.08267] GraphGAN: Graph Representation Learning with Generative Adversarial Nets

著者

Hongwei Wang, Jia Wang, Jialin Wang, Miao Zhao, Weinan Zhang, Fuzheng Zhang, Xing Xie, Minyi Guo

背景

Graph representation learning、もしくはnetwork embeddingはグラフ内のノードを低次元のベクトルとして表現することを目的としている。 これは、実アプリケーションとして、link predictionやnode classification、recommendation、visualization、ナレッジグラフ表現、クラスタリング、ソーシャル分析と幅広く使用されている。

Graph representation learningには生成モデル(generative)と識別モデル(discriminative)の2種類の手法に大別される。 これらは、おなじ問題に対する別のアプローチであり、共存し得ないモデルとなっていた。

目的とアプローチ

目的

  • Graph representation learningにおける異なる2つの手法を組み合わせた新しい学習方法の構築

アプローチ

  • Graph Generative Adversarial Nets
    • Generative Adversarial NetsをGraph構造に応用

提案手法

GraphGAN Framework

グラフ構造に関する学習は、生成モデル(generative)と識別モデル(discriminative)の2つに大別される。 それらを組み合わせたGraphGANを提案する。 GraphGANの概要を下記に示す。

f:id:nogawanogawa:20181224090725j:plain:w600

GraphGANでは、着目するノードv_cの周辺について、v_cと結合しているノードを出力する関数p_{true}からサンプリングしたものと、Gによって生成されたノードを混ぜ込ませる。 これを、グラフ構造全体の妥当性を識別するDiscriminatorに判定させLossを計算することで学習進める。 最終的にはGp_{true}が親しくなることが期待される。

学習全体としてのアルゴリズムを下記に示す。

f:id:nogawanogawa:20181224103548j:plain:w500

Generatorによって生成されたノードをDiscriminatorが妥当性について識別する。これをLossが収束するまで繰り返すアルゴリズムとなる。

Generatorについて詳細を確認する。 既存のグラフ全体からノードの存在確率を学習することで、もっともらしいノードを既存のグラフに挿入し、もっともらしくエッジで結合させる。 アルゴリズムについて下記に示す。

f:id:nogawanogawa:20181224103516j:plain:w500

上のアルゴリズムを概念図で示すと下記のようになる。

f:id:nogawanogawa:20181224103526j:plain:w500

着目ノードに関する結合可能性を示したp_{c}を使用して着目点周辺についてノードを生成していく。

Generatorとは異なり、Discriminatorでは2つのノードのペアに関するエッジの存在確率を考慮する。 2つのノードのペアを入力として、エッジの存在確率を推論する関数を設定することでDiscriminatorとする。

f:id:nogawanogawa:20181224111434j:plain:w500

Discriminator Optimization

Discriminatorは2つのノードを入力に対して、エッジの存在確率を推定する。 GraphGANではDiscriuminatorの関数Dは下記のような関数を使用する。

D(v, v_{c}) = \sigma(\bf{d}_{v}^{T} \bf{d}_{v_c}) = \frac{1}{1 + exp(-\bf{d}_{v}^{T} \bf{d}_{v_c})}

ここで\bf{d}はk次元のベクトルを表している。 Discriminatorは、\bf{d}内積を使用したsigmoid関数を使用する。 GraphGAN全体に関するLossは下記のように設定する。

vが実際のグラフの中に含まれるとき:

\nabla _{\theta_D}V(G, D) = \nabla _{\theta_D}log D(v, v_c)

vがGeneratorによって生成されたフェイクのとき:

\nabla _{\theta_D}V(G, D) = \nabla _{\theta_D}(1- log D(v, v_c))

と表現される。

Generator Optimization

Generatorに関するLossは下記のように設定する。(導出は省略)

\nabla _{\theta_G}V(G, D) = \sum^{V}_{c=1}\mathbb{E}_{v~G(\cdot | v_c)} [  \nabla _{\theta_G} log G (v|v_c) (1- log D(v, v_c))]

これは、log G (v|v_c)  によって重み付けされた確率(logで表現) (1- log D(v, v_c))とみなすことができる。 Dは上で紹介した通りとして、Gに関しては下記のようなSoftmax関数の形式で表される。

G(v|v_c) = \frac{exp(\bf{g}_{v}^{T} \bf{g}_{v_c})}{\sum_{v \neq v_c} exp(\bf{g}_{v}^{T} \bf{g}_{v_c})}

しかし、上の式には2つの課題が考えられる。

  • 計算効率が悪い
  • グラフの結合関係が持つ情報を欠落させてしまう

これらを解決するため、グラフ構造に適した形式のGraph Softmax関数を導入する。

Graph Softmax関数

Graph Softmax関数は下記の3つの特徴を満たすものとする。

  • 正規化
  • グラフ構造の考慮
  • 高い計算効率

Graph Softmax関数では、初めに着目ノードを視点とした幅優先探索を行い、BFS-tree(T_c)を得る。 得られたBFS-treeのうち、着目ノードの近傍のノードとその子ノードの集合をN_c(v)とする。 これを踏まえて条件付き確率pは、次のように書き直される。

p_c(v_i|v) = \frac{exp(\bf{g}_{v}^{T} \bf{g}_{v_c})}{\sum_{v_j \in N_c(v)} exp(\bf{g}_{v_j}^{T} \bf{g}_{v})}

上の条件付き確率を用いてGraph Softmax関数は下記のように表現される。

G(v|v_c) \triangleq \prod ^m_{j=1} p_c(v_{r_{j}}|v_{r_{j-1}})) \cdot p_c(v_{r_{m-1}}|v_{r_{m}}))

上の式では、v_{r_0} = v_cv_{r_m} = vとなっており、先の特徴はGraph Softmax関数によって満たされる。(証明は論文参照)

以上を考慮した際の実際の流れを下記に示す。

f:id:nogawanogawa:20181224090742j:plain

上で示したアルゴリズムを使用し、ランダムウォークによって進行を決定しながらノードの生成・識別を行っていく。 (通常のGANと異なり、GeneratorとDiscriminatorは交互に計算、パラメータの更新を行っていく)

評価

評価環境

データセット

比較対象

  • DeepWalk
  • LINE
  • Node2vec
  • Struc2vec

その他

  • 学習率:0.001
  • イテレーションごと、サンプルは20生成し、Generator/Discriminatorは30回ずつそれぞれ実行する
  • k = 20 (ノードの次元数)

Empirical Study

与えられたノードのペアに関して、エッジの存在確率が対象の近傍でどのように変化するかについて評価する。 ランダムに集めたarXiv-AstroPhおよびarXiv-GrQcノード1,000,000個に対してGraphGANを適用する。

結果を下記に示す。

f:id:nogawanogawa:20181224090755j:plain:w500

近傍から離れた地点において、エッジの存在確率が急激に減少していることから、対象のノードに結合しているノードだけを推定できている事がわかる。(間にノードが1つ以上入るものを除外できている)

エッジの存在推定に関する評価を行う。 評価には、何も手をかけていない教師データを学習に使用し、本来存在するエッジ10%をわざと除去したテストデータを評価として使用する。

結果を下記に示す。

f:id:nogawanogawa:20181224185935j:plain:w400

GraphGANは、比較対象に比べて精度良くエッジを推定できていることがわかる。 2つのモデルを組み合わせた結果、精度を向上させることに成功していると考えられる。

より直感的に理解するために、学習曲線を下記に示す。

f:id:nogawanogawa:20181224090805j:plain:w500

Generatorは開始直後に急速に学習をとげ、すぐに収束した。 一方Discriminatorは、最初精度を急速にあげた後、わずかずつ精度を低下させていった。 これは問題はなく、Generatorが精度良くfakeのノードを生成できているためである。

Node Classification

ノードが持つラベル情報の分類に関する評価を行う。 評価には、何も手をかけていない教師データを学習に使用し、ロジスティック回帰で分類した値を評価に使用する。

結果を下記に示す。

f:id:nogawanogawa:20181224185945j:plain:w400

GraphGANが最も精度良く分類されていることがわかる。 これにより、GraphGANは他の手法より正確にノードを分類できることがわかった。

Recommendation

Movielens-1Mを使用して評価を行う。 4つ星から5つ星の映画に関してグラフを作成し、そのうちランダムに10%のエッジを除去したデータを作成した。

学習の後、ユーザーが見たことのない映画の中で推定された上位K個を抽出してレコメンデーションを行う。

レコメンデーションの評価結果を下記に示す。

f:id:nogawanogawa:20181224090818j:plain:w500

他の手法よりも、Precision/Recallともに優れた値を示しており、GraphGANの有用性が示された。

結論

Graph representation learningに対する異なるアプローチであったgenerativeモデルとdiscriminativeモデルに対し、これらをmi-max gameとして組み合わせたGraphGANを提案した。 また、それに伴いグラフ構造に適合するようにGraph softmaxも導入した。 GraphGANのアーキテクチャにより、GeneratorもDiscriminatorも相乗効果による性能向上が見られることを確認した。 性能評価により、既存の敵対性フレームワークや近接を考慮したモデルと比較しても高い性能が見られることが確認され、本提案手法の有用性が示された。

感想

この前のKDDの論文と比べると、よりアカデミックな話でした。

tsunotsuno.hatenablog.com

GANをグラフ構造に応用することで、グラフ構造が従う支配的な法則(傾向?)をそのまま学習させるということなんでしょう。 実装は想像できそうにありませんが、一応こんな感じらしいです。

github.com

非常に勉強になりました。

全然関係ないけど今日はクリスマスイブでしたか。メリークリスマース。。。