Graph Neural Networkの処理と効果を理解する: How Powerful are Graph Neural Networks?

Graph Neural Networkはどんな処理を行っていて、それによりどんな識別が可能になるのか？という点を検証した論文”How Powerful are Graph Neural Networks?”があったため、読んでみました。本論文はICLR 2019にOralでAcceptされています。

本論文の主張をまとめると、以下のようになります。

• Graph Neural Networkの処理は3段階に分けられる。隣接ノードの集約(AGGREGATE)、集約結果による更新(COMBINE)、そしてグラフ全体の性質を得るためのノード特徴の集約(READOUT)の3つである。
• グラフの類似性を比較するために、ノードの接続種別ごとにラベルを振り、その個数を数え上げ比較する手法がある(Weisfeiler-Lehman Graph Isomorphism Test)。この文脈においては、同じ接続を持つものは同じラベル、異なる接続を持つものは異なるラベルになることが好ましい(単射=injective)。
• よって、AGGREGATE/COMBINE/READOUTの各所において、単射性を崩さないよう気を払う必要がある。AGGREGATEでMEANやMAXを取ってしまうと、接続数が異なるがMEAN/MAXが同じになるケースが区別できない(SUMなら接続数分増加するのでOK)。
• ただ、接続数が多すぎてノイズを取りたい場合や(3Dのポイントクラウドなど)、接続構造ではなく接続先ノードの分布が重要である場合はこの限りではない。

SUMが好ましい、というのはちょうどテキスト分類で試していた結果と同じなので驚きました。論文ではこの理論に則りSUMベースのシンプルなGraph Neural Networkを作成し(Graph Isomorphism Network (GIN))、各種データセットでSOTAと同等/それ以上のスコアを出しています。

以下では、論文のポイントと考察について記載しています。

1. Graph Neural Networkの処理の抽象化
2. Weisfeiler-Lehman Graph Isomorphism Test
3. 自然言語処理への応用において考えるべきこと

Graph Neural Networkの処理の抽象化

Graph Neural Networkは、主にノードの分類かグラフの分類を目的とします。そのためにノード/グラフの表現を計算するわけですが、この処理は以下の3ステップに分けられます。

1. AGGREGATE: 隣接ノードの情報を集約する
2. COMBINE: 集約したノードの情報から、ノード特徴を更新する
3. READOUT: グラフ内のノードから、グラフ全体の表現を得る

GraphSAGEの場合: AGGREGATE=重みを掛けた上でReLU+Maxpooling、COMBINE=重みをかけて結合
Graph Convolutional Networks(GCN)の場合: AGGREGATE=隣接ノードのMEAN、COMBINE=重みを掛けてReLU

という形になっています。READOUTは合計か特殊なPoolingが使用されているそうです。

Weisfeiler-Lehman Graph Isomorphism Test

本論文の肝となっているのが、Weisfeiler-Lehman Graph Isomorphism Testです。これは、グラフ同士がどれくらい似ているのかを計測するための手法です。ノードをリスト化し(List)、接続種別ごとに集約し(Compress)、集約単位(カテゴリ)のラベルをノードに付与します(Relabel)。これを繰り返すと、更新された周辺ノードのラベルが次の更新に影響を与えることになる、つまり遠いノードの情報も加味できるようになります。この点はGraph Convolution (Neural Network)によく似ています。

The Weisfeiler-Lehman Kernel p12より

• Compress: 同じ接続を持つものについて「一意」のラベルを割り振る
• Relabel: ノードに割り当てられるラベルは「一つだけ」

この2点は、ノードとラベルの関係が単射(=injective)であることを意味します。Graph Neural Networkの各処理においても、この制約を満たさない限りはWeisfeiler-Lehmanと同等の識別性は得られません。論文中のLemma 2~ではこの点が検証されています。

大きなポイントとして、SUM以外のAggregationを行うと単射性が崩れるという点です。MAX/MEANの場合、以下のような識別できないグラフ構造が発生します。

How Powerful are Graph Neural Networks? Figure 3より

いずれも、接続ノードの「個数」についての情報が落ちてしまいます(個数は異なるが同じMAX/MEANのケースが識別できない)。ただ、意図的に個数の情報を減らしたい場合はこの限りではありません。

論文中では、この理論に則りSUMベースのシンプルなGraph Neural Networkを作成し(Graph Isomorphism Network (GIN))、各種データセットでSOTAと同等/それ以上のスコアを出しています。

自然言語処理への応用において考えるべきこと

では、自然言語処理においてMAX/MEANを取ったほうが良いケースはあるのでしょうか。

まず、自然言語処理ではグラフの構造で文を識別しようとしていません。係り受けの場合、係り受けの形いかんでテキスト分類の結果が違う、というのは考えずらいです。これは、単語同士の類似度についても同じです。そのため、グラフの構造を意識しなければならない=SUMを取る必要は必ずしもないと考えられます。ただ、単語の数は重要な情報の一つなので、少なくともREADOUTの際にSUMを取るのは有効と考えられます。

自然言語処理では、Graph Neural Networkをグラフの分類としてもノードの分類としても使っていません。その意味では、単に隣接行列の情報だけあればよく、Graph Neural Networkの識別力を使っていないのではとも考えられます。Graph Neural Networkを上手く使うなら、グラフかノードの識別問題に持ち込む必要があるのでは？という気がします。この点は今後検討していこうと思います。