書誌情報

著者：Kun Xu, Lingfei Wu, Zhiguo Wang, Yansong Feng, Michael Witbrock, Vadim Sheinin
所属：IBM Research
arXiv: 2018/5/25

概要

グラフ構造から出力センテンスを生成する graph-to-sequence neural encoder-decoder architecture を提案
- 既存のグラフ情報をシーケンスに落としてから Seq2Seq にかけるアプローチではグラフの情報が失われてしまう
- 入力センテンスの句構造情報を抽出して用いる Tree2Seq [17] や，入力センテンスを木構造として階層的にencode する方法も提案されている[19,20]が，こうしたモデルは適用対象が限定され，グラフ構造一般の問題に適用可能ではない
bAbI task19, グラフからの最短経路抽出, SQLからの質問文生成タスクにおいて，既存のグラフ構造を考慮した GraphConvolutionNetwork 等を上回るパフォーマンスを示した．

Graph2Seq model

モデルは３つの要素から構成される

1. Node Embedding

入力グラフから，各node を表現するベクトルを計算

2. Graph Embedding

node embedding をまとめてグラフ全体を表現とするベクトルを計算する

3. Attention based decoder

Graph Embedding を入力とする Attention付きDecoder
Node embedding に対して各ステップでAttention を計算

Node Embedding Generation

ノード $v$ のテキスト情報とEmbedding行列 $W_e$ から特徴ベクトル$a_v$ を作成
ノード $v$ に隣接するノードを forward neighbors $N_{\vdash}(v)$, backward neighbors $N_{\dashv}(v)$ に分類
- $N_{\vdash}(v)$ : 有向グラフにおいて，ノード $v$ からエッジが出ているノード群
- $N_{\dashv}(v)$ : 有向グラフにおいて, ノード $v$ へとエッジを出しているノード群
ノード $v$ のforward neighbors の k-1 ステップでの forward representation $h^{k-1}_{u\vdash}, \forall u \in N_{\vdash}(v) $　を一つにまとめたベクトル neighborhood vector $h^k_{N(v)}$ を作成する
- k はイテレーションの回数を示している
- 一つにまとめる操作を $\mathrm{AGGREGATE}^{\vdash}_k$ とよび，いくつかの種類を試す
ノード $v$ の現在の forward representation $h^{k-1}_{v\vdash}$ と，ステップ３で作成した neighborhood vector $h^k_{N\vdash(v)}$ を Concat する．このConcat したベクトルを非線形な活性化関数を持つ全結合NN に入力して得られた出力をノード $v$ の新たな forward representation $h^k_{v\vdash}$ とする．
同様にしてノード $v$ のbackward representation $h^k_{v\dashv}$ を更新する
ステップ 3~5 を $K$ 回繰り返す. 最後に得られたノード $v$ の forward representation と backward representation を Concat したものをノード $v$ の表現ベクトル(node embedding)とする

Aggregator Architectures

隣接するノードの表現ベクトルを用いて１つのベクトルを作成する方法(AGGREGATOR)にバリエーションを用意して検証した．

Mean aggregator : 隣接するノードの表現ベクトルを平均したものを出力する
LSTM aggregator : LSTM に隣接するノードの表現ベクトルをランダムな順番で入力し，最後のLSTMセルの隠れ状態を出力とする
Pooling aggregator : 隣接ノードの表現ベクトルそれぞれを全結合層に入れ，出力ベクトルを各要素毎に max-pooling したものを出力とする

Graph Embedding Generation

node embedding からグラフ全体の情報を表す graph embedding を作成する

Pooling-based Graph Embedding

node embedding をそれぞれ全結合層に入れ，出力を要素ごとに max-pooling, min-pooling, もしくは averatge-pooling したものを graph embedding とした．実験した結果ときにさはなかったので max-pooling をデフォルトとした

Node-based Graph Embedding

入力グラフに，全てのノードから入力を受ける super node $v_s$ を追加
node embedding の計算の際に同様に $v_s$ のembedding も計算し, それを graph-embedding とした

Attention Based Decoder

Graph embedding を入力とするRNNモデルで decodeする
従来のAttention モデル同様，1ステップ前の decoder隠れ状態と, 各ノードの表現ベクトルから $z_i$ アテンションを計算．計算した attention から $z_i$ を重み付き和したベクトル $c_i$（コンテキスト）を計算し，RNN出力の計算に使用
ビームサイズ=5

c\_i = \sum^{V}_{j=1}\alpha_{ij}z_j, where \alpha_{ij}=\frac{\mathrm{exp}(e_{ij})}{\sum^{V}_{k=1}\mathrm{exp}(e_{ik})}, e_{ij} = a(s_{i-1}, z_j)

実験結果

bAbI Task 19

bABi artificial intelligence task：AI の推論能力を測るためのタスク
Task19(Path Finding)
- 自然文で場所の位置関係が与えられ，ある場所から別の場所に行くための経路を答える課題 (Fig2 を参照)
モデルに合わせてデータを整形
- 入力される場所の相対的な位置関係をグラフ化 (各場所をノード，位置関係をエッジとした)
  - 例: A west B -> ノード A からノード B に向かってエッジ west が張られているグラフ
  - タスクは相対的な位置情報から構築されるグラフにおいて，ある２つのノード間の最短経路を求める問題とみなせる
- 質問文がノード $N_{o1}$ からノード $N_{o2}$ への最短経路を求める場合 $N_{o1}$, $N_{o2}$ の text attribute を START, END とし，他のノードの text attribute はグラフ内のID とした
- 各エッジはノードに変換し，エッジのテキストをそのノードの text attribute とした．
  - エッジもノード化することで node embedding で node 同様に扱う
GraphConvolutionNetwork は sequence decoder と組み合わせることでシーケンスを出力させた．

結果

Graph2Seqモデルが最も高い精度を示した(Table1, bAbIT19 列)
- GCN は無効グラフに対してデザインされており，有効エッジの情報が失われてしまうために Graph2Seqよりも精度が低くなっていると考えられる

Shortest Path Task

ランダムに生成した有効グラフの中で２つのノードの最短パスを見つけるタスク
データセットの作成：ランダムにグラフを作成し，その中から２つのノードを選択
- 最短パスは１経路のみであるとする
- Small(node数=5, 最短パス長>=2), Large(node数=100, 最短パス長>=4) の２種類の設定で作成

結果

Graph2Seqモデルが最も高い精度を示した(Table1, SP-S, SP-L 列)
- GGS_NN は長い距離の依存関係を扱うことが難しいため Large グラフで精度が低下
- GCN は有向グラフを考慮できないため精度が下がる
  - 有効性を考慮できないのであればもっと低くなってもおかしくないのでは？？

Natural Language Generation Task

SQL を文章に変換するタスク
- graph-to-sequence モデルを意味構造を表現するグラフに対して適用
WikiSQLデータ・セットを使用
- 87,726 の人手で作成された自然言語質問文と，対応するSQLのデータセット
- SQL を入力として，正しい英語の質問文を生成するタスクとした（本来は逆の用途で作成された）
- BLEU4 スコアで評価
各モデルに合わせて入力を加工
- Tree2Seq : SQL を木構造に変換した上で入力

結果

Graph2Seq が最も高い精度示した (Table2)
- Tree2Seq の tree encoder では子ノードの情報しか統合できず，親ノードの情報が失われてしまうため，精度が低くなったと考えられる

Aggregator と Hop Size について Shortest Path Taskで比較

Mean Aggregator が最も高いパフォーマンスを示した
Hopサイズが大きくなるほど精度は向上 (ノード数1000のグラフで実験)
- forward, backward 両方の情報を用いる MA が Hop数に対して高いパフォーマンスを示す
- Graph2Seqでは hop数を大きくすれば全て同じパフォーマンスに収束

Methodの違い
- MA=mean aggregator, LA=LSTM, PA=Pooling, MA-F=mean aggregator with forward repr only
各列の違い
- DAG : directed acyclic graph, グラフ内に循環が存在しない
- DCG : directed cyclic graph, グラフ内に循環が存在
- SEQ : sequence, グラフは一本の線になっている