グラフニューラルネットワーク(1)概要

グラフニューラルネットワーク(1)概要

“グラフ理論と機械学習“より

第一章 序論(グラフ理論の基礎)より、wikiの定義では「グラフ理論とはノード(頂点)の集合とエッジ(辺)の集合で構成されるグラフに関する数学の理論である。グラフデータ構造などの応用がある」となる。データの構造としては以下に示すものとなる(wikiより)

上図は6つのノード(頂点)と7つのエッジ(辺)にて成り立っている。またこれは以下に示すような隣接行列で表すことができる。

\begin{eqnarray}
\left(
\begin{array}{ccc}
0 & 1 & 0 & 0 & 1 & 0\\
1 & 0 & 1 & 0 & 1 & 0\\
0 & 0 & 0 & 1 & 0 & 0\\
0 & 0 & 1 & 0 & 1 & 1\\
1 & 1 & 0 & 1 & 0 & 0\\
0 & 0 & 0 & 1 & 0 & 0
\end{array}
\right)
\end{eqnarray}

また、このグラフを数学的に表すと、グラフの集合G={V,E}に対して、V={1,2,3,4,5,6}、E={(1,2),(1,5),(2,3),(2,5),(3,4),(4,5),(4,6)}のように表すことができる。ここではグラフと無向グラフとして(1,2)と(2,1)は同等と見做し、省略している。有向グラフの場合は(1,2)と(2,1)はそれぞれ区別される。また、ノードの近傍を表す集合N(v)として、N(1)={2,5}、N(2)={1,3,5}、N(5)={1,2,4}のように表すことができる。

更に、それぞれのノードが複数の属性を持ち{数学的には、𝐗∈𝑅^nxdで表される。n個のノードがそれぞれd個の特徴量を持つ)、それらがMessage Passingに基づいてノード間でやり取りされるモデルが、グラフィカルモデルや、機械学習の視点で考えられる。

ここで機械学習とグラフの関係について考えると、一つの側面は以下に示すようなフロー(計算手順)を表す(プロセスの可視化)という観点がある。

このような特徴を活かして、例えばtensflowではTensorBoradによる演算の可視化が行われる。またグラフィカルモデルにおいても、確率の複雑なフローを可視化することで処理を理解しミスが生じないようにすることができる。

また、画像データをグラフ的に見るという観点も存在する。これは例えば以下の左図に示すような規則正しい網目上に表現されたデータ(ユークリッド空間上のデータ)として表される。

これに対して、グラフの畳み込み処理は右図に示されるような不規則な処理となり、非ユークリッド空間上での処理となることが言える。畳み込み処理は周辺の情報参考にして値を作る処理であり、ユークリッド空間上では上下左右という位置情報に意味を持たせているのに対して、非ユークリッド空間上での処理では隣接しているかどうかの情報のみが重要になる。

次に自然言語処理とグラフの関係を考える。例えば文書の中に2つの単語が出てきた際にそれを共起と呼び、エッジとして表現したものを共起ネットワークと呼び、以下のように示すことができる。(K-Hコーダーによるデータ処理例)

このような単語の間の関係を示すようなグラフを使うことで、単語の意味や、文章の意味を分析することができる。また、BOWにCos類似度を用いることで、下図に示すような文書間の類似度の計算をすることもできる。

また近年では、言語処理への深層学習の導入として、Attensionという処理をベースとしたTransformerというモジュールを中心に研究が進められている。トランスフォーマーは以下に示すようなブロック図で表され、

それぞれの単語をノードと見做し、そのノード(単語)が隠れ層として特徴量(図中の青とオレンジ)を持つ、ここでAttensionとして重要なものに対して重みづけを行い、それらを周りの単語群の中での畳み込みとして計算することで、各単語が持つ重みづけを計算するアルゴリズムとなる。このアテンションを使った隠れ層の重みづけを学習するTransformerアルゴリズムはBERTの中でも用いられ、大きな成果を出している。

上記のように深層学習をグラフに導入するアプローチはGraph Neural Network(GNN)として近年盛んに研究されている。これはざっくりと言うと、「画像のような規則正しいデータの制約を外して、隣接行列ベースで近傍を考えて学習するもの」となる。この学習するメカニズムとして単純な畳み込みではなく、メッセージ伝搬をベースしたグラフ畳み込みを行なっていることがGNNの特徴となる。

ここで言うメッセージ伝搬とは、以下に示されるような式で定義される。

\begin{eqnarray}
Edge-wise:m_e^{(t+1)}=\phi(x_v^{(t)}, x_u^{(t)}, w_e^{(t)}), (v, u, e) \in E \\[5pt] Node-wise:x_v^{(t+1)}=\psi(x_v^{(t)}, \rho(\{m_e^{(t+1)} : (v, u, e) \in E \}))
\end{eqnarray}

この式は、直接的にエッジを持つ近傍のノード同士が情報を交換し、時間が経つにつれて全体に情報が行き渡るものを表している。

ここで、上記のメッセージ伝搬的な考えた方を使ったアルゴリズムとして「グラフ畳み込み(graph convolution)」がある。グラフ畳み込みとは、以下に示すようにあるノードv1に対して、そのノードが持つ隠れ層\(h_1^{new}\)を計算するときに、近隣のノードの和を計算した上で関数f(シグモイド関数等)で演算するという以前一般化線形モデル(GLM)で述べたモデルとなる。

一般的な画像データに対する畳み込み(convolution)では、それぞれの画素のピクセルにその周辺のピクセルの値を重み付けして足し合わせる操作を行なっているのに対して、グラフの場合は注目ノードの周辺ノードの接続関係が不定形である可能性がある。

それらを解決する為2つのアプローチがある。一つは、グラフ上の信号(各ノードに割り当てられた特徴ベクター)をベースにグラフフーリエ変換を行うことで、隣接行列からラプラシアン行列を生成して計算を行うことがグラフ畳み込みの特徴となるもので、もう一つは以下に示すような形でノードに接続した信号をGLM的な手法で計算するものとなる。

\[ h_i^{(l+1)}=\sigma (\displaystyle \sum_{r\in R}\sum_{j\in N_i^r} \frac{1}{c_{i,r}}W_r^{(l)}h_j^{(l)}+W_0^{(l)}h_i^{(l)})\]

上記のような仕組みを用いて、化合物の物性推定を従来より30万倍高速に処理できたとする報告(Googleによる報告)がある。これはMPNN,(Message Passing Neural Networks framework)とよばれるフレームワークで、(1)message (近傍からどんな情報を取得するか)、(2)update (messageからどのように信号を更新するか)、(3)readout (グラフの信号から「グラフ自体」の特徴をどう読み取るか)の3つの要素に整理した上で学習されている。

今回はグラフニューラルネットワークの概要について述べた。次回は、それらを処理するツールであるDeep Graph Libraryを使った実際のデータ処理について述べてみたい。