Open agatan opened 5 years ago
semi-supervised node classification のために PageRank と GNN を組み合わせようという話。 （グラフ中の一部ノードにのみラベルが与えられているとき、全ノードを正しく classification したい。というタスク）
O(n^2)
Graph Convolutional Network (GCN) は以下のような式で定義される（2 層の場合）。
ここで、 A は normalize された隣接行列, X は feature matrix, W はパラメータ。 直感的には、一層ごとに自身の feature と隣接ノードの feature の平均を取るようなイメージ。
問題は
GCN の層を増やしていくと、propagate の分布は PageRank に似た分布に近づいていく。 PageRank は
を無限 step 計算したときの \pi で、
\pi
を無限 step 繰り返したときの分布と一致する。 (GCN との違いは self loop の扱いと normalize の方法だけ。)
が、PageRank は Graph 全体に対するプロパティであり、各ノードに focus したものではない。 そこで Personalized PageRank を使うというアイディアが出てくる。
x は root node, i_x は teleport vector (personalize vector) でここでは [0, 0, ..., 1, 0, ...] のように「自分自身が 1, それ以外は 0」であるような要素 n のベクトル。 Personalized PageRank は「確率 1 - α でランダムウォーク、確率 α で自分自身に戻る」を無限に繰り返したときの分布。 全ノードから見た Personalized PageRank を計算する必要があるので大変。
[0, 0, ..., 1, 0, ...]
ノードを別個で predict する Network に通した後、周辺にその結果を propagate する PPNP を提案している。
PPNP は Personalized PageRank を使っているが、全ノードごとに Personalized PageRank を作ると NxN の Dense Matrix を作る必要があるし時間計算量も N^2 でかかってくる。
NxN
N^2
そこで、topic-sensitive PageRank 的な考え方を活用することで近似しつつ計算量を落とす。 （topic-sensitive PageRank は、topic ごとに teleport vector が定義されるような PageRank。今回の提案手法は topic-sensitive PageRank そのものではない。）
K step の power iteration で近似する。（収束したかどうかは見ない。常に固定回数）
State of the Art の精度を出している。 PubMed などはグラフが大きいので PPNP は計算できない。が、APPNP は計算可能で性能もよかった。
学習時間はシンプルな GCN よりは遅いが、GAT などよりは速い。
APPNP の power iteration 数と精度の分析。 最適な K は、max(ラベルのあるノードとの shortest path distance for node in all nodes) と大体同じになっているらしい。
max(ラベルのあるノードとの shortest path distance for node in all nodes)
「propagate をどのタイミングで活用するか」についての分析。 propagate しない、training 時のみ、inference 時のみ、両方、の 4 pattern ある。
semi-supervised node classification のために PageRank と GNN を組み合わせようという話。 （グラフ中の一部ノードにのみラベルが与えられているとき、全ノードを正しく classification したい。というタスク）
概要
O(n^2)なので計算量がつらい。Topic-Sensitive PageRank で近似することで精度を保ちつつ計算量を抑えることができた （APPNP）GCN の問題点
Graph Convolutional Network (GCN) は以下のような式で定義される（2 層の場合）。
ここで、 A は normalize された隣接行列, X は feature matrix, W はパラメータ。 直感的には、一層ごとに自身の feature と隣接ノードの feature の平均を取るようなイメージ。
問題は
Personalized PageRank の活用
GCN の層を増やしていくと、propagate の分布は PageRank に似た分布に近づいていく。 PageRank は
を無限 step 計算したときの
\piで、を無限 step 繰り返したときの分布と一致する。 (GCN との違いは self loop の扱いと normalize の方法だけ。)
が、PageRank は Graph 全体に対するプロパティであり、各ノードに focus したものではない。 そこで Personalized PageRank を使うというアイディアが出てくる。
x は root node, i_x は teleport vector (personalize vector) でここでは
[0, 0, ..., 1, 0, ...]のように「自分自身が 1, それ以外は 0」であるような要素 n のベクトル。 Personalized PageRank は「確率 1 - α でランダムウォーク、確率 α で自分自身に戻る」を無限に繰り返したときの分布。 全ノードから見た Personalized PageRank を計算する必要があるので大変。Personalized propagation of neural predictions (PPNP)
ノードを別個で predict する Network に通した後、周辺にその結果を propagate する PPNP を提案している。
Approximate personalized propagation of neural predictions (APPNP)
PPNP は Personalized PageRank を使っているが、全ノードごとに Personalized PageRank を作ると
NxNの Dense Matrix を作る必要があるし時間計算量もN^2でかかってくる。そこで、topic-sensitive PageRank 的な考え方を活用することで近似しつつ計算量を落とす。 （topic-sensitive PageRank は、topic ごとに teleport vector が定義されるような PageRank。今回の提案手法は topic-sensitive PageRank そのものではない。）
K step の power iteration で近似する。（収束したかどうかは見ない。常に固定回数）
評価
State of the Art の精度を出している。 PubMed などはグラフが大きいので PPNP は計算できない。が、APPNP は計算可能で性能もよかった。
学習時間はシンプルな GCN よりは遅いが、GAT などよりは速い。
APPNP の power iteration 数と精度の分析。 最適な K は、
max(ラベルのあるノードとの shortest path distance for node in all nodes)と大体同じになっているらしい。「propagate をどのタイミングで活用するか」についての分析。 propagate しない、training 時のみ、inference 時のみ、両方、の 4 pattern ある。