Higher-order Graph Convolutional Networksを読んだのでメモ
はじめに
Higher-order Graph Convolutional Networksを読んだのでメモ
気持ち
現状のgraph convolutional networks(GCN)はone-hopの隣接関係のみを考慮したものになっていて,高次の情報を捉え切れていない.そこでmulti-hopな重み付き隣接行列を使ったGCNを提案するというもの.
Graph Self-Attention Layer
KipfとWellingが提案した多層のGCNは次の形で表現される.(この論文は前に読んでメモを残した)
ここでは自己ループを加えた隣接行列ではを使って計算された度数行列.はグラフのノードが持つ層目の特徴ベクトルでは学習パラメータ.
ここでは正規化された対称行列で,これはone-hopな隣接関係にあるノードの重み付き和を表現していることになる.そのためノードに隣接したノード集合を使えば次のように書き直せる.
は正規化の部分にあたる項.
上記のGCNのを次のようなネットワークの推論結果に置き換えるGraph Attention Networks (GAT)というものも提案されている.
アテンションベクトルは学習パラメータ.細かいところはまた今度論文読む.
Convolutional Layer with Motif Attention
ここから論文の貢献部分.GCNもGATもone-hopしか見ないため,ノードの隣接関係が常に最適とは限らない(Fig 2に簡単な例が図解されてる).そこでここではmotif(グラフの隣接関係のpriorのようなもの)を導入して様々な隣接関係を考慮する(motifについてはFig 1の(d)に例が示されている).
ノード,エッジで定義されるグラフと,個のmotif が与えられた時,motifに対応した個の隣接行列を構成する.隣接行列が計算できると,motif-induced neighborhoods を定義することができ,この隣接関係を用いてGCNの計算を行うことで様々な隣接関係を考慮した畳み込みが可能.
ここでで定義されるmotif-based matrix formulationを導入する.関数が与えられた時,motif-based matrices を得ることが可能.以下に,の様々な表現をまとめる.
Unweighted Motif Adjacency w/ Self-loops
最も単純な形として次のような隣接行列が考えられる.
ただしこれは重みを考慮しない分,motif-induced adjacencyを十分に活用できない.
Weighted Motif Adjacency w/ Row-wise Max
Motif adjacencyの重みを保持した次のような表現が考えられる.
は対角行列でその対角成分はで定義される.これは自己ループに隣接ノードの中で最も重要度の高いノードと同様の重要度を割り当てることを意味する.
Motif Transition w/ Row-wise Max
自己ループに行方向の最大値を割り当てた重み付きグラフ上でのランダムウォークの遷移行列はで定義される.すると,次のようなrandom walk motif transition matrixが定義できる.
Absolute Motif Laplacian
Absolute Laplacian matrixを次のように定義する.
この表現は自己ループの重要度が隣接ノードの重要度の和で定義されるため,自己ループを重要視しやすくなる.
Symmetric Normalized Matrix w/ Row-wise Max
次のようなsymmetric normalized matrixを計算することもできる.
以上がこの論文で定義されている5パターンのの表現.さらにステップサイズが与えられた元で,-step motif-based matricesを各個のmotifについて定義する.
の場合,より広い範囲のノード(-hopの隣接ノード)から情報を集約することができる.
ここで,ステップサイズと個の異なるmotifが与えられた時,ステップサイズとmotif毎に個別にGCNの計算を行い,最終層で特徴ベクトルを結合することが考えられる.ただし単純に結合すると特徴ベクトルが大きくなりすぎるという問題がある.そこでアテンション構造を各層に導入して重み付き和をとることでこれを回避する.
まず,第層にと,の二つの関数を導入する.は第層における状態空間で,関数の出力はsoftmax関数を通って確率表現になっている.これはノードの状態が与えられた時,ノードに最も関連のあるmotif とステップサイズを推薦することを意味する.
さらに二つの行列を結合して作られるstate matrixを定義する.
は入力を次元に埋め込む重み行列で,はone-hopの隣接関係から得られる局所的な情報を含んだ行列.はmotif count matrixで各ノードが所属している個の異なるmotifを数えることによって局所的な構造に関する情報を与えていて,最初にあらかじめ計算される.
ここで,をmotif probabilitiesとし,をステップサイズのためのprobability vectorとする.をの最大値のインデックスとし,をの最大値のインデックスとすれば,アテンションは次のような行列で定義できる.
この層ごとに計算される行列をGCNのの代わりに使うことでMotif Convolutional Networksが計算される.
まとめ
ヒューリスティックな手法と理論由来な手法が融合したような感じ.ただ,隣接行列に関して motifとステップの組み合わせぶん計算するせいで,の隣接行列が必要になるからかなりの計算コストになりそう.