Graph Convolutionを自然言語処理に応用する Part1

piqcy
piqcy
Aug 31, 2018 · 7 min read

Graph Convolutionを自然言語処理に応用するため、何回かに分けて学習した内容をまとめていきます。内容については、最終的にQiitaなどで1記事にまとめる予定です。

Part1では、Graphを扱う過去の手法からGraph Convolutionへと到るまでの過程を解説します。また、Graph Convolutionに着目した理由についても述べておきます。

なぜ自然言語でGraph Convolutionか

Graph Convolutionに着目した理由はTransformerです。Transformerで使用されているSelf-Attentionは、各単語が他の全単語とどれくらい関係しているかの重みを算出します。これは、単語をノードとみなすとまさにグラフ構造のような形になります。

Attention-based Models (DLAI D8L 2017 UPC Deep Learning for Artificial Intelligence)

そのため、グラフ系の手法は自然言語に応用可能ではないかと考えています。そして、Graph Convolutionはグラフの特徴を抽出するのに今最も注目されている手法です。そこで、この技術を深掘りし学んで行くことにしました。

Graph Convolutionの歴史

最初に、そもそもGraphの特徴を扱うのにどういった手法があったのかを紹介します。大まかには、以下のような流れになっています。

  1. GraphへのNeural Networkの適用
    The graph neural network model: 周辺ノード・エッジの特徴をニューラルネットへの入力とし、ノードの状態(隠れ層)を一定回数更新する。ノードの特徴以外に(周辺情報を加味した)状態を利用することで、グラフ内のノード検索の精度が上がることを確認
  2. GraphにCNNを適用する方法の検討
    Spectral Networks and Locally Connected Networks on Graphs: ノードに対し、クラスタリング=>クラスタ特徴の抽出=>さらにクラスタリング・・・と繰り返すことで低位=>上位への特徴を抽出するCNNを模すことができると提案。クラスタリングとしてSpectral Clusteringの手法を利用しており、ここからSpectral系の手法が生まれた。Spectral Clusteringは固有値分解を基にしたクラスタリングの手法で、Spectral系の手法は固有値分解と計算処理が等価なフーリエ級数展開(Graph Fourie)を使用して演算を行う。
  3. Spectralの、Spatialへの合流
    Semi-Supervised Classification with Graph Convolutional Networks: シンプルな周辺ノードの畳み込みにより、Spectral Methodの演算結果を近似できることが証明される。
  4. 発展期
    重たいSpectralの手法に依存しなくてよくなったため、活用が広がる。Graph Attention Networksは、他分野で注目されていたAttentionをGraph Networkに適用した手法。

この流れは、以下のスライドによくまとまっています。

Structured deep models: Deep learning on graphs and beyond

また、こちらのスライドでも解説を行なっています。

上記の通り、“Graph Convolution”には大きく2つの手法があります。ストレートに周辺ノードの情報を「同じ重みで」(=同じFilterによる処理)畳み込む手法であるSpatial Methodと、クラスタリング(固有値分解)を基にしたSpectral Methodです。Graph Convolutionと聞いた場合には、それがどちらを指しているのかに注意を払う必要があります。

Graph Convolutionの仕組み

ここからは、現在・また今後も主流になるであろうSpatial Methodに絞って解説を行います。

Spatial Methodで畳み込みを行う場合は、以下のように周辺ノードからノードの潜在表現を得ます。この時、周辺ノードに適用する重みは同じW1が使われています。この点をもって、「畳み込み」的な処理としています。

Structured deep models: Deep learning on graphs and beyond

これでノードの表現は獲得できますが、エッジの表現は獲得できません。グラフにおいてはエッジの情報も重要です(AさんとBさんが友達なのか兄弟なのかなど)。そのため、エッジの情報についても推定する手法が考案されました。

手法としては、ノードの推定を行う際にエッジの潜在表現を経由します。まずNodeの潜在表現からEdgeの潜在表現を生成し(v->e)、周辺ノードの潜在表現とエッジの潜在表現を掛け合わせることで対象ノードの潜在表現を作成しています(e->v)。

Structured deep models: Deep learning on graphs and beyond

同様にエッジの情報を推論する手法としては、知識グラフ(Knowledge Base)にGCNを応用したModeling Relational Data with Graph Convolutional Networksがあります。

ただ、この場合エッジの表現にノードの表現が依存することになり、計算が煩雑で大規模なグラフには適用しづらくなります。そこで、エッジの表現を単純にAttentionの重みで表現する手法が編み出されました。それがGraph Attention Networkです。

Structured deep models: Deep learning on graphs and beyond

エッジの表現力は弱まりますが、その分より早く演算が可能です。

  1. 演算は高速だがエッジの情報は取れないGCN
  2. エッジの情報をリッチにとれるが、演算は遅くなりあまり大規模なネットワークには適用できないGNN(Edge/Relationalと呼ばれたりもする)
  3. ある程度エッジの情報もとれ、演算速度もそこそこなGraph Attention Network

このうちどれを使うかは、トレードオフを加味して決めることになります。また、”Graph Convolution”と聞いたときは、エッジの情報がどのように処理されているのかについて注意を払う必要があります(考慮しない・潜在表現として扱う・考慮するけど潜在表現までにはしない)。

この後のPart2では、実際にGraph Convolutionの実装を確認していきたいと思います。

参考文献

programming-soda

Exciting research & programming like soda!

piqcy

Written by

piqcy

All change is not growth, as all movement is not forward. Ellen Glasgow

programming-soda

Exciting research & programming like soda!

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade