はじめに

Graph U-Netsを読んだのでメモ．

概要

Graph Neural NetworkでU-Netを作りたいというもの．そのためにgraph Pooling (gPool)とgraph Unpool (gUnpool)を提案する．

Graph Pooling Layer

ここでの目標は，グラフから情報量の多いノードをサンプリングして部分集合を得ること．学習パラメータ $\mathbf{p}$ ，ノード上の特徴ベクトルを $\mathbf{x}_i$ で定義して，ノードの情報量を次のスカラー値で定義する．

$\displaystyle y_i=\mathbf{x}_i\mathbf{p}/\|\mathbf{p}\|$

最終的に $y_i$ が大きいノードをサンプリングして新たなグラフを得る．

より具体的な話に入るためいくつかの変数を導入する．ここでは $N$ 個のノードを持つグラフ $\mathbb{G}$ を考え，このグラフは隣接行列 $A^l\in\mathbb{R}^{N\times N}$ とノード上の $C$ 次元特徴ベクトルを表す特徴行列を $X^l\in\mathbb{R}^{N\times C}$ として定義する．

すると，graph pooling layerは次のように定義される．

$\displaystyle \mathbf{y}=X^l\mathbf{p}^l/\|\mathbf{p}^l\|,\\ \mathrm{idx}=\mathrm{rank}(\mathbf{y},k),\\ \tilde{\mathbf{y}}=\mathrm{sigmoid}(\mathbf{y}(\mathrm{idx})),\\ \tilde{x}^l=X^l(\mathrm{idx},:),\\ A^{l+1}=A^l(\mathrm{idx},\mathrm{idx}),\\ X^{l+1}=\tilde{X}^l\odot(\tilde{\mathbf{y}}\mathbf{1}^T_C)$

2式目のrankは $\mathbf{y}$ から値の大きいtop-kのインデックスを選択する関数で， $(\mathrm{idx},:)$ や $(\mathrm{idx},\mathrm{idx})$ は $X,A$ からidx番目の要素を取り出すことを意味する．最後の式は，取り出された各ノードの値に情報量を表す量 $\mathbf{y}$ を乗じる演算を表している．

上記の定式化により学習パラメータ $\mathbf{p}$ はbackpropで学習可能．ただこれでより良いノードを選択可能な写像になる気はしないがどうなのか．

Graph Unpooling Layer

基本的な戦略はgPoolの逆関数を定義しようというもの．ここでは次のような定式化を考える．

$\displaystyle X^{l+1}=\mathrm{distribute}(0_{N\times C},X^l,\mathrm{idx})$

$\mathrm{idx}\in\mathbb{Z}^{\ast k}$ は対応する解像度（ $N$ ノードから $k$ ノードへのdownsampling）のgPoolで選ばれたノードのインデックスを表す． $X^l\in\mathbb{R}^{k\times C}$ は現在のグラフにおける特徴行列で $0_{N\times C}$ は新たなグラフの特徴行列の初期値（全ての要素が0の $N\times C$ 行列）． $\mathrm{distribute}$ は $X^l$ の要素を $\mathrm{idx}$ を元に $0_{N\times C}$ にコピーしていくというもの．非常にstraightforwardな手法．