タイトル : Semi-Supervised Classification with Graph Convolutional Networks

著者
- Thomas N. Kipf (1)
- Max Welling (1, 2)

1 University of Amsterdam

2 Canadian Institute for Advanced Research (CIFAR)

ICLR2017

Graph系でよく見かける人たち.

↓本論文 [1609.02907] Semi-Supervised Classification with Graph Convolutional Networks (ICLR 2017)

概要

グラフ上のノードを分類する問題で, ラベルが一部にしかついていないような問題を考える. これはグラフの半教師付き学習の枠組みに入る. これまではラベルの情報はグラフラプラシアン正則化として、損失関数の中に入れられていた.

$\begin{equation} \mathcal L = \mathcal L_{0}+\lambda\mathcal L_{reg}, \ \ \ \ \ with \ \mathcal L_{reg} = \sum_{i,j}{A_{ij}||f(X_i)-f(X_j)}||^{2}=f(X)^{T}\Delta f(X), \end{equation}$

$\mathcal L_{0}$ はラベルがついてる部分の損失関数. 注目すべきなのは正則化項として隣接頂点が同じラベルじゃなければペナルティが与えられてる点で, これは隣接頂点は同じラベルになるだろうっていう仮定の正則化だが, 実際ノード間のエッジは必ずしも類似性を表現してるわけではないから, あまりよくない制約を入れてしまっていることになる. そこで,本論文では, グラフ上に直接ニューラルネットワークを構築して損失関数に明示的にグラフベースの正則化を入れない方法を提案する. 提案手法はスペクトラルグラフコンボリューションの一次近接性に着想を得ているらしい →

[0912.3848] Wavelets on Graphs via Spectral Graph Theory (全く読んでいない. ←読んだ(2018年12月), 重要なところはchebyshevの多項式を使って, グラフラプラシアンの対角化を避けて対角化する内容を提案した論文(多分))

(グラフにおける近接性の話は時々でてくる.

Understanding Large Social Networks

[1503.03578] LINE: Large-scale Information Network Embedding この辺りが有名 ) 提案手法は高速で, 大規模実行可能, 半教師付き学習として分類精度及び速度でSOTAを上回る.

背景

ノードの分類問題は重要だけど,ラベルをちょっとしか持ってない場合があり,そういう問題に取り組む.

提案手法

色々な手法が紹介されているが, ここでは論文内で最も優れているとされた手法を載せる.

$\begin{equation} Z = \tilde{D}^{\frac{1}{2}}\tilde{A}\tilde{D}^{\frac{1}{2}}X\Theta, \end{equation}$

ここで, $\tilde{A}, \tilde{D}$ はそれぞれ $\begin{equation}\tilde{A}=A+I_{N}, \tilde{D_{ii}}=\sum_{j}{\tilde{A}_{ij}}, \end{equation}$ で、 $A$ はグラフの隣接行列, $I_{N}$ は単位行列 (グラフ的に考えると, 各ノードの自己ループを表す行列).

$\Theta$ は $C×F$ のパラメータ, $Z$ は $N×F$ の単純に出力結果 ( $C$ が各ノードの特徴ベクトルの次元, $F$ がクラス数, $N$ がサンプル数).

一応これでも何をやってるかは大体分かるが, 多分以下の式の方が分かりやすい. 本論文中で実際に用いられたアーキテクチャ.

$\begin{equation} Z = f(X,A) = \rm{softmax}(\hat{A}\rm{ReLU}(\hat{A}XW^{(0)})W^{(1)}), \end{equation}$

ここで, $\begin{equation} \hat{A} = \tilde{D}^{\frac{1}{2}}\tilde{A}\tilde{D}^{\frac{1}{2}} \end{equation}$ で, これは前もって計算しとく.

各 $W$ は重みパラメータで, 以下の目的関数を小さくするために最適化する.

$\begin{equation} \mathcal L = -{\displaystyle \sum_{l \in \mathcal Y_{L}}}{\displaystyle \sum_{f=1}^{F}}{Y_{lf}\rm{ln}\it{Z_{lf}}}, \end{equation}$

ここで, $\mathcal Y_{L}$ はラベル付きノード集合. 以下論文の画像. f:id:banana_88:20180822204317p:plain

すごい単純に解釈すると, ネットワーク内でそれぞれのノードに各層で共通の重みパラメータを与えてることが, 高速化と大規模実行可能に繋がってると言っている (多分).

実験

実験で用いたデータセットは以下.

引用ネットワークと知識グラフを使っている. f:id:banana_88:20180823163951p:plain

実験結果は以下. f:id:banana_88:20180823164224p:plain

これまでのグラフラプラシアンに基づく方法は, エッジがノードの類似性を示しているという仮定を置いていた (すなわちノード間にエッジがあればその2つのノードは似ているはずという仮定). またDeepWalkとかnode2vecとかもランダムウォークして特徴生成する過程と訓練する過程が分断されてしまって, それぞれ独立に最適化してしまっているという問題があった. 提案手法ではこれらの問題点を克服し, 性能と速度両方の面で優れていた.

参考

https://arxiv.org/pdf/1609.02907.pdf

Semi-Supervised Classification with Graph Convolutional Networksのまとめ - Qiita