Graph Networkについて｜Graph Neural Networkの理解を試みる #2

f:id:lib-arts:20210502163018p:plain

Graph Neural Networkの理解を試みるシリーズです。#1では"Graph Neural Networks: A Review of Methods and Applications"を元にGraph Neural Networkの構造について確認を行いました。

途中で出てきたGraph NetworkはオーソドックスなGNNであるMPNN(Message Passing Neural Network)やTransformerなどが含まれるNLNN(Non-Local Neural Network)を統合するフレームワークとされていましたが、Surveyの記述だけでは意味が掴めなかったので、#2ではGraph Networkの元の論文である、"Relational inductive biases, deep learning, and graph networks"を確認します。

[1806.01261] Relational inductive biases, deep learning, and graph networks

以下、当記事の目次になります。
1. 論文の概要把握(Abstract〜Section2)
2. Graph Networkに関して(Section3)
3. まとめ

1. 論文の概要把握(Abstract〜Section2)
1節では論文の概要の把握について行います。まず論文のタイトルに記載されている、"relational inductive biases"はこの論文を読み解くにあたっての重要なポイントなのでこちらから確認します。

f:id:lib-arts:20210502163709p:plain
上記は論文のAbstractの記載ですが、2つ目のパラグラフに"relational inductive biases"が記載されているので青でハイライトを行いました。また、ここで関連で抑えておくと良い表現が"combinatorial generalization"(組み合わせ的一般化)や"structured representations"(構造の表現)です。

上記の記事でも確認しましたが、GNNはCNNやRNNなどと比較するというよりはもう少し下のレイヤーの考え方であると考えて良いと思われます。ユークリッド空間的な処理に基づくCNNやRNNとは異なり、GNNはより自由度の高い表現が可能です。"relational inductive biases"はCNNやRNNにおいてCNNは近傍、 RNNは系列のように計算過程に制約を設けることと考えて良いかと思います。「バイアス」については先入観のニュアンスで考えがちですが、ここでの"inductive bias"はどちらかというと「制約を設けることで学習アルゴリズムが優先度に基づいて学習を行うことができる」という意味合いで理解しておくと良さそうです。

f:id:lib-arts:20210502170014p:plain

上記は論文のTable1ですが、"relational inductive biases"については上記で確認すると良いかと思います。Fully connectedの処理は"All-to-All"の処理を行うため、"relational inductive biases"があまり生じず、計算効率があまりよくないと考えて良さそうです。一方で、CNNでは局所性(Locality)、RNNでは系列性(Sequentiality)の"relational inductive biases"が生じ、タスクに対応していると考えて良いかと思います。また、Graph networkは任意(Arbitrary)とされており、CNNやRNNよりも表現力が高いと考えて良いかと思います。

f:id:lib-arts:20210502170401p:plain

また、Fully connected layers、Convolutional layers、Recurrent layersなどそれぞれの処理における再利用やパラメータシェアリングについては上記のように論文のFigure.1で記載されています。

2. Graph Networkに関して(Section3)
2節ではGraph Networkに関して取り扱います。

f:id:lib-arts:20210502180728p:plain

Graphの定義については#1の記事でも取り扱いましたが、元論文のBox3で概要が記載されています。ノードが $\mathbf{v}_k$ 、エッジが $\mathbf{e}_k$ 、グラフ全体の属性が $\mathbf{u}$ であると把握しておけば良いかと思います。ここで $\mathbf{u}$ についてはあまり見ないですが、グラフ分類(Graph Classification)のタスクの出力と同様に把握しておけば良いかと思います。以下ではGraph Networkのモジュール(GN block)の処理概要について確認を行います。

f:id:lib-arts:20210502181046p:plain

GN blockは上記のような関数を含むとされています。"update function"の $\phi$ と"aggregation function"の $\rho$ で構成されるとあります。いまいち処理の全容がわからないので、GN blockの処理について記載されているAlgorithm_1を確認します。

f:id:lib-arts:20210502181413p:plain

上記のAlgorithm_1の記載では、6つの処理が記載されています。1〜3は各層において主にノードの属性を更新していく処理で、4〜6はグラフ分類(Graph Classification)タスクのように、ノードやエッジの値を集約してグラフ全体に対して何らかの推論を行う処理と理解すると良いかと思います。

f:id:lib-arts:20210502182030p:plain
"update function"の $\phi$ については上記で示した論文のFigure_3で記載されており、それぞれ水色で表されたところが更新されていると理解すると良いかと思います。

f:id:lib-arts:20210502182254p:plain

ここまでの内容は少し抽象的でしたが、Figure_4では具体的なネットワーク構造を元に取りまとめが行われています。MPNN(Message Passing Neural Network)が(c)、NLNN(Non-Local Neural Network)が(d)で表現されていることを確認しておくと良いかと思います。

Graph Networkはこのような設定によって、Graph Neural Networkに関する処理を包括的に取り扱えるようなGN blockを定義し、整理をおこなったものと理解しておくと良いかと思います。

3. まとめ
#2ではGraph Networkについて取り扱った、"Relational inductive biases, deep learning, and graph networks"を確認しました。抽象的な記載でなかなか理解が大変な内容ではありますが、元論文では図が多く記載されていたので大まかには把握できたのではないかと思います。
#3ではGraph Networkの表記についてより理解するにあたって、2節で取り扱ったFigure_4をより具体的に確認していければと思います。