Summary

乱立しているGNNを一つの枠組みで解析・整理した上で、その理論上最も強力なモデルやその条件を提唱し、実際に良い性能が得られることを確認した論文。

Contributionは次の4つ。

グラフの構造を識別する能力において、(後で定義する)GNNのクラスの能力が高々WL-test(後述)以下であることを示した。
グラフの構造を識別する能力がWL-testと同等となるためのGNNに対する条件を示した。
有名なGNN(GCN, GraphSAGE)が区別できないグラフ構造の例を示した。
提案するGIN(Graph Isomorphism Network)がWL-testと同等の能力をもつことを示した。

Preliminaries

GNNの定義

GNNのクラスを、その特徴量 $h_v ^ {(k)}$ を次のように計算するモデルの集合と定める。

\begin{align} a _ v ^ {(k)} &= AGGREGATE ^ {(k)} (\left\{ h _ u ^ {(k - 1)} | u \in N(v) \right\}) \\ h _ v ^ {(k)} &= COMBINE ^ {(k)} ( h _ v ^ {(k - 1)}, a _ v {(k)}) \end{align}

$\left\{ h _ u ^ {(k - 1)} | u \in N(v) \right\}$ は頂点 $v$ の近傍の特徴量のmultiset(重複を許容する集合)を示しており、このように近傍頂点に対する畳み込みをmultiset上の演算と同一視することができる。

GraphSAGEは

\begin{align} AGGREGATE ^ {(k)} &= MAX \circ ReLU \circ W \\ COMBINE ^ {(k)} &= W \circ CONCAT \end{align}

で、GCNは

\begin{align} AGGREGATE ^ {(k)} &= ReLU \circ W \circ MEAN \\ COMBINE ^ {(k)} &= I \end{align}

で定式化できる。*1

WL-test

特徴量を離散空間に限定し、multisetとみなした近傍頂点の特徴量集合に対して、固有のラベルを割り当てることを考える。これは近傍頂点を根つき木として展開した際に、それぞれの木に固有のラベルをつけて区別することを意味する。

f:id:ey_nosukeru:20190523150723p:plain — 近傍を根つき木として展開する

k近傍まで展開した時の特徴量のmultisetを順次比較することで、2つのグラフが等しいかどうかを判定できる。

WL-testは少しでも違う近傍集合を別のものとして区別できるため、グラフ構造の区別能力においては理論上最強である。

Proposed Method

提案手法では

GNNで区別できるグラフはWL-testでも区別できること
AGGREGATEやCOMBINEが単射であれば、GNNの構造識別能力はWL-testと同等になること

を証明とともに示している。つまりGNNの識別能力についてはAGGREGATEやCOMBINEが単射であること(違うmultisetについてその特徴量も異なること)が重要であると主張している。

さらに、この枠組みのもとで、次の集約関数

\begin{align} h _ v ^ {(k)} = \phi ^ {(k)} \biggl((1 + \epsilon ^ {(k)}) h _ v ^ {(k - 1)} + \sum _ {u \in N(v)} h _ u ^ {(k - 1)} \biggr) \end{align}

( $\phi ^ {(k)}$ : 2層以上のMLP)によって定義されるGNNであるGINを提案し、この識別能力がWL-testと同等であることを示している。

また $MAX, MEAN, SUM$ という3つの集約関数に関して、具体的にそれぞれが区別できないようなグラフの構造を示すことでその能力の大小について議論している。

f:id:ey_nosukeru:20190523152816p:plain — meanやmaxが識別できないmultisetの例。1つ目はmeanもmaxも「どちらも青1」という出力になる。同様に真ん中は「緑1赤1」、右は「緑1赤1」となって区別できない。

f:id:ey_nosukeru:20190523152617p:plain — maxは各要素が存在しているかどうかしか判定できないが、meanはその割合まで判定できる。sumはそれぞれの具体的な数まで区別できる。

Results

f:id:ey_nosukeru:20190523153051p:plain — 性能比較。GNN variantsはAGGREGATEやCOMBINEに名前がどんな関数を使ったかを表している。GIN-0は $\epsilon ^ {(k)} = 0$ とした場合。

性能比較。GNN variantsはAGGREGATEやCOMBINEに名前がどんな関数を使ったかを表している。GIN-0は $\epsilon ^ {(k)} = 0$ とした場合。

多くの場合で提案手法が良い性能を示している。 $\epsilon = 0$ の方が全体的に良い性能を出しているのは学習の安定性の問題か。

感想

$\epsilon$ を学習させずに適当な値( $\epsilon = 0.01$ とか)で学習した場合の結果や、本当にグラフ構造の識別構造だけがGNNの性能に影響するのか(汎化性能、似たものを同一視する能力は？)は疑問の残るところではありますが、GNN全体を論理立てて概観できた感がありとても参考になりました。