[Paper]GCN

sngmng6506·2022년 11월 24일
0

SEMI-SUPERVISED CLASSIFICATION WITH GRAPH CONVOLUTIONAL NETWORKS
https://arxiv.org/pdf/1609.02907v4.pdf

Propagation

GCN에는 다음과 같은 propagation rule(layer-wise)이 존재한다.

A~\tilde{A} = A+INA + I_N : undirected graph G에 self-connection을 추가한 것
AA : adjacency matrix
σ\sigma : activation function
D~\tilde{D} : degree matrix
W(l)W^{(l)} : layer-specific learnable weight matrix
H(0)H^{(0)} = XX

해당 propagation rule은 first-order approximation of localized spectral filters on graph에 의해 motivated 되었다.
https://arxiv.org/pdf/1606.09375.pdf

SPECTRAL GRAPH CONVOLUTIONS

논문에서 말하는 convolution 연산은 다음과 같은 eigen decompostion을 말한다 ΛUTx\Lambda U^Tx : 푸리에 변환

위의 propagation rule을 고려하면, L:=IND1/2AD1/2=UΛUTL := I_N - D^{-1/2}AD^{-1/2} = U\Lambda U^T 라고 표현할 수 있다.

UU : normalized된 Laplacian의 eigenvector들로 구성된 matrix
Laplacian matrix = Degree matrix - Adjacency matrix
UU를 구하는 computational cost = O(N2)\mathcal{O}(N^2)
Λ\Lambda의 cost도 비싸기 때문에 아래와 같은 근사법이 제시됨.

[-1,1] 범위의 Orthogonal basis인 K번째 chebyshev polnomial TkT_k까지만 고려해서 근사한다.

11Tn(x)Tm(x)dx1x2\int_{-1}^{1} T_n(x)T_m(x) {dx \over \sqrt{1-x^2}} = 0 (n != m)
θk\theta_k : k번째 basis 방향으로 내적 coefficient

예를들어, λmax=2\lambda_{max} = 2 & k=1인경우는다음과같다.k = 1 인 경우는 다음과 같다.

T0=1T_0 = 1
T1=xT_1 = x

profile
개인 공부 기록용

0개의 댓글