はじめに

Higher-order Graph Convolutional Networksを読んだのでメモ

気持ち

現状のgraph convolutional networks（GCN）はone-hopの隣接関係のみを考慮したものになっていて，高次の情報を捉え切れていない．そこでmulti-hopな重み付き隣接行列を使ったGCNを提案するというもの．

Graph Self-Attention Layer

KipfとWellingが提案した多層のGCNは次の形で表現される．（この論文は前に読んでメモを残した）

$\displaystyle \mathbf{H}^{(l+1)}=\sigma(\tilde{\mathbf{D}}^{-\frac{1}{2}}\tilde{\mathbf{A}}\tilde{\mathbf{D}}^{-\frac{1}{2}}\mathbf{H}^{(l)}\mathbf{W}^{(l)})$

ここで $\tilde{\mathbf{A}}=\mathbf{A}+\mathbf{I}_N$ は自己ループを加えた隣接行列で $\tilde{\mathbf{D}}$ は $\tilde{\mathbf{A}}$ を使って計算された度数行列． $\mathbf{H}^{(l)}$ はグラフのノードが持つ $l$ 層目の特徴ベクトルで $\mathbf{W}^{(l)}$ は学習パラメータ．

ここで $\tilde{\mathbf{D}}^{-\frac{1}{2}}\tilde{\mathbf{A}}\tilde{\mathbf{D}}^{-\frac{1}{2}}$ は正規化された対称行列で，これはone-hopな隣接関係にあるノードの重み付き和を表現していることになる．そのためノード $i$ に隣接したノード集合 $\mathcal{N}_i$ を使えば次のように書き直せる．

$\displaystyle \mathbf{h}_i^{(l+1)}=\sigma\left(\sum_{j\in\mathcal{N}_l^{(\tilde{\mathbf{A}})}}\alpha_{i,j}\mathbf{h}_j^{(l)}\mathbf{W}^{(l)}\right)$

$\alpha_{i,j}=\frac{1}{\sqrt{\mathrm{deg}(i)\mathrm{deg}(j)}}$ は正規化の部分にあたる項．

上記のGCNの $\alpha$ を次のようなネットワークの推論結果に置き換えるGraph Attention Networks (GAT)というものも提案されている．

$\displaystyle \alpha_{i,j}=\frac{\exp\left(\mathrm{LeakyReLU}\left(\mathbf{a}[\mathbf{h}_i\mathbf{W}\mathbf{h}_j\mathbf{W}]\right)\right)}{\sum_{k\in\mathcal{N}_i^{(\tilde{\mathbf{A}})}}\exp\left(\mathrm{LeakyReLU}\left(\mathbf{a}[\mathbf{h}_i\mathbf{W}\mathbf{h}_k\mathbf{W}]\right)\right)}$

アテンションベクトル $\mathbf{a}$ は学習パラメータ．細かいところはまた今度論文読む．

Convolutional Layer with Motif Attention

ここから論文の貢献部分．GCNもGATもone-hopしか見ないため，ノードの隣接関係が常に最適とは限らない（Fig 2に簡単な例が図解されてる）．そこでここではmotif（グラフの隣接関係のpriorのようなもの）を導入して様々な隣接関係を考慮する（motifについてはFig 1の(d)に例が示されている）．

ノード $N=|\mathcal{V}|$ ，エッジ $M=|\mathcal{E}|$ で定義されるグラフ $\mathcal{g}=(\mathcal{V},\mathcal{E})$ と， $T$ 個のmotif $\mathcal{H}=\{H_1,\dots,H_T\}$ が与えられた時，motifに対応した $T$ 個の隣接行列 $\mathcal{A}=\{\mathbf{A}_1,\dots,\mathbf{A}_T\}$ を構成する．隣接行列が計算できると，motif-induced neighborhoods $\mathcal{N}_i^{(\mathbf{A}_t)}$ を定義することができ，この隣接関係を用いてGCNの計算を行うことで様々な隣接関係を考慮した畳み込みが可能．

ここで $\Psi:\mathbb{R}^{N\times N}\rightarrow\mathbb{R}^{N\times N}$ で定義されるmotif-based matrix formulationを導入する．関数 $\Psi$ が与えられた時，motif-based matrices $\tilde{\mathbf{A}}_t=\Psi(\mathbf{A}_t)$ を得ることが可能．以下に， $\Psi$ の様々な表現をまとめる．

Unweighted Motif Adjacency w/ Self-loops

最も単純な形として次のような隣接行列が考えられる．

$\displaystyle \tilde{\mathbf{A}}_{i,j}=\left\{ \begin{matrix} 1\:\:i=j \\ 1\:\:\mathbf{A}_{i,j}\gt 0 \\ 0\:\:\mathrm{otherwise} \end{matrix}\right.$

ただしこれは重みを考慮しない分，motif-induced adjacencyを十分に活用できない．

Weighted Motif Adjacency w/ Row-wise Max

Motif adjacencyの重みを保持した次のような表現が考えられる．

$\displaystyle \tilde{\mathbf{A}}=\mathbf{A}+\mathbf{M}$

$\mathbf{M}$ は対角行列でその対角成分は $M_{i,j}=\max_{1\leq j\leq N}A_{i,j}$ で定義される．これは自己ループに隣接ノードの中で最も重要度の高いノードと同様の重要度を割り当てることを意味する．

Motif Transition w/ Row-wise Max

自己ループに行方向の最大値を割り当てた重み付きグラフ上でのランダムウォークの遷移行列は $P_{i,j}=\frac{A_{i,j}}{(\sum_kA_{i,k})+(\max_{1\leq k\leq N}A_{i,k})}$ で定義される．すると，次のようなrandom walk motif transition matrixが定義できる．

$\displaystyle \tilde{\mathbf{A}}=\mathbf{D}^{-1}(\mathbf{A}+\mathbf{M})=\mathbf{P}$

Absolute Motif Laplacian

Absolute Laplacian matrixを次のように定義する．

$\displaystyle \tilde{\mathbf{A}}=\mathbf{D}+\mathbf{A}$

この表現は自己ループの重要度が隣接ノードの重要度の和で定義されるため，自己ループを重要視しやすくなる．

Symmetric Normalized Matrix w/ Row-wise Max

次のようなsymmetric normalized matrixを計算することもできる．

$\displaystyle \tilde{\mathbf{A}}=\mathbf{D}^{-\frac{1}{2}}(\mathbf{A}+\mathbf{M})\mathbf{D}^{-\frac{1}{2}}$

以上がこの論文で定義されている５パターンの $\Psi$ の表現．さらにステップサイズ $K$ が与えられた元で， $k$ -step motif-based matricesを各 $T$ 個のmotifについて定義する．

$\displaystyle \tilde{\mathbf{A}}_t^{(k)}=\Psi(\mathbf{A}_t^k),\:\mathrm{for}\:k=1,\dots,K\:\mathrm{and}\:t=1,\dots,T\\ \mathrm{where}\\ \Psi(\mathbf{A}_t^k)=\Psi(\underbrace{\mathbf{A}_t,\dots,\mathbf{A}_t}_{k})$

$K\gt 1$ の場合，より広い範囲のノード（ $k$ -hopの隣接ノード）から情報を集約することができる．

ここで，ステップサイズ $K$ と $T$ 個の異なるmotifが与えられた時，ステップサイズとmotif毎に個別にGCNの計算を行い，最終層で特徴ベクトルを結合することが考えられる．ただし単純に結合すると特徴ベクトルが大きくなりすぎるという問題がある．そこでアテンション構造を各層に導入して重み付き和をとることでこれを回避する．

まず，第 $l$ 層に $f_l:\mathbb{R}^{S_l}\rightarrow\mathbb{R}^T$ と， $f_l':\mathbb{R}^{S_l}\times\mathbb{R}^T\rightarrow\mathbb{R}^K$ の二つの関数を導入する． $S_l$ は第 $l$ 層における状態空間で，関数の出力はsoftmax関数を通って確率表現になっている．これはノード $i$ の状態が与えられた時，ノード $i$ に最も関連のあるmotif $t$ とステップサイズ $k$ を推薦することを意味する．

さらに二つの行列を結合して作られるstate matrixを定義する．

$\displaystyle \mathbf{S}_l=\left[\Psi(\mathbf{A})\mathbf{H}^{(l)}\mathbf{W}^{(l)}\:\mathbf{C}\right]$

$\mathbf{W}^{(l)}\in\mathbb{R}^{N\times D_l}$ は入力を $D_l$ 次元に埋め込む重み行列で， $\Psi(\mathbf{A})\mathbf{H}^{(l)}\mathbf{W}^{(l)}$ はone-hopの隣接関係から得られる局所的な情報を含んだ行列． $\mathbf{C}\in\mathbb{R}^{N\times C}$ はmotif count matrixで各ノードが所属している $C$ 個の異なるmotifを数えることによって局所的な構造に関する情報を与えていて，最初にあらかじめ計算される．

ここで， $\mathbf{f}_i=f(\mathbf{s}_i)$ をmotif probabilitiesとし， $\mathbf{f}_i'=f'(\mathbf{s}_i,\mathbf{f}_i)$ をステップサイズのためのprobability vectorとする． $t_i$ を $\mathbf{f}_i$ の最大値のインデックスとし， $k_i$ を $\mathbf{f}_i'$ の最大値のインデックスとすれば，アテンションは次のような $N\times N$ 行列で定義できる．

$\displaystyle \hat{\mathbf{A}}=\left[ \begin{matrix} \left(\tilde{\mathbf{A}}_{t_1}^{k_1}\right)_{1,:}\\ \vdots\\ \left(\tilde{\mathbf{A}}_{t_N}^{(k_N)}\right)_{N,:} \end{matrix} \right]$