Semi-Supervised Classification with Graph Convolutional Networks
석사과정을 시작하던 시절, 본격적으로 논문들을 review하던 중 deep-dive를 했던 논문 중 하나.
당시엔 notion의 존재를 모르기도 했고, (현재까지) 태블릿이 없기도 해서 프린트로 출력 후 논문에 직접 써가며 review를 했었던 기억이 난다.
(notion의 존재를 좀 더 빨리 알았더라면 re-posting도 수월했을텐데..)
tensorflow v1으로 작성된 코드를 논문과 비교하면서 해석해보고, 어찌저찌 실행도 해보고, 원 저자의 pytorch 구현을 참고해서 pytorch로 다시 작성해보고...
여러모로 추억이 많은 논문인 듯 하다.
Published in ICLR2017
- paper: https://arxiv.org/abs/1609.02907
- official source code repo (tensorflow v1): https://github.com/tkipf/gcn
- commented source code repo (tensorflow v1)
- re-built source code repo (pytorch)
graph의 edge 수에 따라 선형적으로 확장 가능한 semi-supervised learning 방법(GCN)을 소개.
hidden layer는 node의 feature와 그래프의 지역적인(local) 구조를 encode하여 그에 해당하는 representation을 학습하는 것이 가능.
Introduction
graph-based semi-supervised learning을 언급한다.
graph-based semi-supervised learning이 무엇일까?
graph의 모든 node마다 label 정보가 포함되어 있지 않고 일부의 node만이 label 정보를 가지고 있어, 해당 node들을 통해 node representation을 학습하여 label이 없는 node들에 대한 generalization(일반화)을 하는 것이 주 목적이라고 생각할 수 있을 것이다.
이를 하게 되면 뭐가 좋을까?
대표적으로 학습된 representation들을 통해 주어진 node가 어떤 label에 속하는 지를 판단하는 node classification task를 수행할 수가 있고, 논문의 첫 문장에서도 "classifying nodes (such as documents) in a graph (such as a citation network)." 를 언급하여 node classification task를 고려하기로 한다.
물론 과거에도 node classificaiton task를 해결하기 위한 여러 시도들이 있었고, 해당 연구들은 주로 graph Laplacian regularization term을 loss function에 추가하여 학습을 진행했다.
$\mathcal{L_{reg}}$의 몇몇 부분을 보자.
$f(\cdot)$ 이 미분 가능한 함수(e.g. neural network), $\lambda$는 단순 factor, $X$는 node feature vector 로 구성된 feature matrix, 그리고 $\Delta$는 $\Delta = D - A$로 이뤄지는 unnormalized graph Laplacian이다.
여기서 $D$는 각 node들의 차수(degree)를 나타내는 차수 행렬(degree matrix) 이고, $A$는 각 node들 간의 연결 정보를 binary하게 표현한 인접 행렬(adjacency matrix) 이다.
unnormalized graph Laplacian 이 무엇일까?
식을 보면 말 그대로 인접 행렬과 차수 행렬을 이용하여, graph의 구조적인 정보를 조금이나마 더 담아낸 행렬로 생각할 수 있다.
여기서 문제점이 발생한다.
식1은 연결된 node끼리는 같은 label을 공유한다 라는 가정을 전제 하에 두고 있다는 점이다.
이는 graph의 edge가 node 간의 유사성을 직접적으로 encode하지는 않지만, node간의 유사성은 추가적인 정보를 포함할 수 있기에 modeling capacity를 제한할 수 있다.
이게 무슨 의미 일까?
label은 동일하지만, 거리가 멀리 떨어진 두 node간의 유사성 정보를 반영하지 못할 수 있다.
즉 이러한 가정을 갖고 modeling을 수행할 경우, 복잡한 graph 또는 다양한 label을 가진 graph에서 모델의 학습 성능이 저하될 수 있다는 의미일 것이다.
따라서 본 논문에서는 graph의 구조를 곧바로 encode할 수 있는 방법과 더불어 크게 2개의 contribution을 소개한다.
- graph에 바로 적용될 수 있는 neural network를 위한 간단한 layer-wise propagation rule을 소개.
- 제안한 graph-based neural network 모델이 semi-supervised node classification task를 빠르고 scalable하게 수행 가능하다는 점을 소개.
Fast Approximate Convolutions on Graphs
논문에서 소개하는 GCN(Graph Convolutional Network)을 간단하게 소개하고, 관련된 이전 연구와 spectral convolution에 대한 background를 언급한다.
논문에서 소개하는 핵심인 layer-wise propagation rule은 다음과 같다.
$\tilde{A}$는 $A + I_N$으로 표현되는 undirected graph의 수정된 인접 행렬.
이때 $I_N$은 항등 행렬(identity matrix)이고 각 node가 자기 자신의 정보를 활용하기 위해 self-connection을 추가 한 형태라고 볼 수 있다.
$\tilde{D_{ij}}$는 $\tilde{A}$의 차수 행렬이고, $W^{(l)}$은 layer-specific weight matrix이다.
$H^{(l)}$은 $l$번째 layer의 activation matrix, 즉 $H^{(0)} = X$ (node feature matrix)가 된다.
논문에서는 식2의 propagation rule이 선행 연구인 [Hammond et al., 2011]과 [Defferrard et al., 2016](ChebNet)과 같이 localized 된 spectral filter의 1차 근사(first order approximation)를 통해 이뤄질 수 있음을 이야기 하고 있다.
선행되었던 두 연구 뿐만이 아니라 Chebyshev polynomials, spectral convolution 등등 알아햐 할 내용이 좀 많은 듯 한데, 이후로는 최대한 내가 이해했던 대로 기술하고자 한다.
review를 하던 당시 내용이 이해가 가질 않아 (조금이나마 이해하는데 도움이 되었 던) 자료를 다시 봐도 좋을 듯 하다:
Spectral Graph Convolutions
Fourier domain에서 정의되며 filter $g_{\theta} = diag(\theta)$를 통한 spectral convolution은 다음과 같이 정의가 가능:
이때 $U$는 대각 성분이 자기 자신의 eigenvalue인 $\Lambda$로 구성된 normalized graph Laplacian $L = I_N - D^{-\frac{1}{2}}A D^{-\frac{1}{2}} = U{\Lambda}U^T$의 eigenvector로 이뤄진 행렬이고, $U^{T}x$는 $x$의 graph Fourier transform이다.
(벌써 어지럽다)
여하튼, 논문에서는 식3의 문제점을 지적하고 있다.
- 이 식을 바로 계산하는 것은 computationally expensive.
($\because$ $D$는 sparse한 eigen matrix) - large graph의 Laplacian $L$을 eigen decomposition하는 것은 expensive.
이처럼 sparse matrix의 직접적인 이용이 힘들었기에, [Hammond et al., 2011]가 다음과 같이 $g_{\theta}(\Lambda)$에 대해 Chebyshev polynomials $T_k(x)$를 $K^{th}$차 까지 확장한다면 적절하게 근사(approximate)할 수 있음을 제안했다.
Chebyshev polynomials는 $T_0(x) = 1$, $T_1(x) = x$, $T_k(x) = 2xT_{k-1}(x) - T_{k-2}(x)$와 같이 recursive한 형태로 정의된다.
(자세한 내용은 [Hammond et al., 2011]의 논문을 참고하라고도 저자가 이야기 하고 있다.)
위의 식4을 이용해 식3을 다시 표현한다면 다음과 같이 근사(approximate)할 수 있다:
이때 $\tilde{L} = \frac{2}{\lambda_{max}}L - I_N$.
이 표현 식은 Laplacian에서 $K$차수 polynomial이기 때문에 $K$-localized된 식 이며, 즉 graph의 한 중심 node에서부터 최대 $K$ step만큼 떨어진 node에만 집중할 수 있으며, 계산 복잡도는 edge 수에 linear한 $\mathcal{O}(|\delta|)$가 된다.
역시 어렵다.
깊게 생각하기 보단, 단순히 기존 spectral convolution on graph의 식3 을 위와 같이 Chebyshev polynomials를 이용해 식5와 같이 approximate 하게 된다면 복잡도를 linear하게 줄일 수 있다는 점을 짚고 가면 될 듯 하다.
[Defferrard et al., 2016](ChebNet)가 선행적으로 이 식을 사용해 graph에 대해 convolutional neural network를 적용하는 방법을 정의하기도 하였다.
Layer-wise Linear Model
식5 형태의 convolutional layer를 여러 층 쌓아 graph convolution에 기반한 neural network model을 설계할 수 있고, 이때 $K=1$로 제한하게 된다면 식5는 선형함수가 된다.
$K=1$이어도 식5의 layer를 여러 층 쌓아서 convolutional filter를 여전히 근사할 수 있지만, Chebyshev polynomials로부터 주어진 명시적 파라미터화(explicit parameterization)의 제약을 받지 않게 된다.
이런 $K=1$인 모델은 wide node degree distribution을 가진 graph(e.g. social network, citation network, 실 세계 graph data 등...)에서 지역적인 이웃 구조(local neighborhood structure)에 overfit하는 문제를 완화할 수 있으며, layer-wise한 선형 연산으로 인해 neural network의 층을 더욱 깊게(deep) 할 수 있다.
neural network의 파라미터가 train하는 동안 적응 및 변화할 것으로 기대하기에 $\lambda_{max} \approx 2$로 근사하게 되면, 식5는 2개의 free parameter $\theta'_0$, $\theta'_1$ 를 이용해 다음과 같이 전개될 수 있다:
filter parameter는 전체 graph에서 공유 가능하며, 이 형태의 filter를 연속적으로($k$번) 적용하게 되면 한 node로 부터 $k$ 거리 만큼 떨어진 이웃까지 잘 convolve할 수 있다.
Chebyshev polynomials
$T_0(x) = 1$, $T_1(x) = x$, $T_k(x) = 2xT_{k-1}(x) - T_{k-2}(x)$를 이용해 $K=1$인 경우를 전개를 해 보면 다음처럼 간단히 전개할 수 있다:
$T_0(\tilde{L}) = 1$
$T_1(\tilde{L}) = \tilde{L}$
그리고 $\tilde{L} = \frac{2}{\lambda_{max}}(L - I_N)$로 정의되었고,
이때 $\lambda_{max} \approx 2$를 적용하면,
$\tilde{L} = L - I_N$ 이므로
$L = I_N - D^{-\frac{1}{2}}A D^{-\frac{1}{2}}$가 된다.
이 결과들을 식5에 적용($K=1$)하면 식6의 형태를 구할 수 있다.
여기서 연산량을 줄이거나 overfitting을 방지하기 위해서 filter parameter를 $\theta$ $=$ $\theta'_0$ $=$ $- \theta'_1$와 같이 간소화 한다면 식6은 다음과 같이 표현될 수 있다:
(단순히 $\theta$를 풀어서 전개하면 이 형태가 나온다.)
하지만 deep neural network에서 이 연산을 반복적으로 수행하는 경우, 수치적으로 불안정할 수 있으며 exploding/vanishing gradient 문제가 발생할 수 있다.
따라서 이를 방지하기 위해 다음과 같은 renormalization trick을 사용한다:
$$I_N + D^{-\frac{1}{2}}A D^{-\frac{1}{2}} \rightarrow \tilde{D}^{-\frac{1}{2}}\tilde{A}\tilde{D}^{-\frac{1}{2}}$$
$$where \ \tilde{A} = A + I_N, \ \tilde{D}_{ij} = \sum_{j} \tilde{A}_{ij}$$
이 trick을 이용해 $C$ input channel을 가진 signal $X \in \mathbb{R}^{N \times C}$ (graph의 각 node마다 $C$ 차원의 feature vector를 가지고 있는 경우)에 일반화를 하면 다음과 같은 형태의 수식을 구할 수 있다:
$\Theta \in \mathbb{R}^{C \times F}$는 filter parameter로 구성된 행렬, $Z \in \mathbb{R}^{N \times F}$는 convolution이 진행 된 signal의 행렬이다.
(즉 $\Theta$가 learnable weight, $Z$가 1번의 layer propagation을 거치고 non-linear activation을 적용하기 이전의 representation이 된다.)
이 filtering operation은 $\mathcal{O}(|\delta|FC)$의 복잡도를 가지며, 인접 행렬(adjacency matrix)과 특징 행렬(feature matrix)의 곱 연산($AX$)은 sparse matrix dense matrix multiplication (SpMM)과 같은 연산을 통해 효율적인 계산이 가능하다.
(몇몇 자료들을 보면 $\sum$ 기호를 이용해 node-level에서 representation을 계산하는 식을 소개하는데(vector-level),
결국 이 vector들을 stack하여 식8과 같이 matrix로 표현한 것일 뿐이다.)
Semi-Supervised Node Classfication
앞서 소개한 내용을 바탕으로 이제 본 논문에서 target으로 잡았던 node classification을 어떻게 handle할 것인지를 소개한다.
논문에서는 graph의 구조적인 정보를 담은 $A$와 주어진 데이터인 $X$에 기반하여 식8 기반의 모델 $f(X, A)$를 conditioning하여 graph-based semi-supervised learning이 가능함을 이야기하고 있다.
semi-supervised learning을 위한 multi-layer GCN의 구조를 그림으로 보면 다음과 같다:
Example
2-layer GCN을 생각해보자.
먼저, 주어진 인접 행렬 $A$를 이용해 $\hat{A} = \tilde{D}^{-\frac{1}{2}}\tilde{A}\tilde{D}^{-\frac{1}{2}}$와 같은 전 처리(pre-process) 과정을 거친 후, 다음의 forward pass를 거치면 된다:
($\tilde{A} = A + I_N, \ \tilde{D}_{ij} = \sum_{j} \tilde{A}_{ij}$)
여기서 $W^{(0)} \in \mathbb{R}^{C \times H}$는 input-hidden 간의 가중치 행렬(weight matrix)이고, $W^{(1)} \in \mathbb{R}^{H \times F}$는 hidden-output 간의 가중치 행렬이다.
그리고 $\mathrm{softmax}$는 $\mathrm{softmax}(x_i) = \frac{1}{\sum_i exp(x_i)}exp(x_i)$인 row-wise로 적용되는 활성화 함수(activation function)이다.
학습을 위한 손실 함수(loss function)는 classification task에서 자주 사용되는 cross-entropy error를 사용하며, label이 포함된 모든 데이터에 대해 계산을 한다면 다음과 같다:
실험에 있어 모든 training iteration마다 full-batch gradient descent를 수행하였고, dropout을 사용하였으며, $A$는 sparse representation을 이용했기에 edge 수 만큼의 공간 복잡도를 가지게 된다.
어떻게 보면 단순하다.
2-layer를 가진다는 의미는 node representation을 계산 할 때 하나의 node로 부터 거리 2(2-hop)만큼 떨어진 노드의 representation을 활용한다는 의미일 것이다.
graph theory에 따르면 인접 행렬 $A$를 여러 번($n$번) 곱한다는 의미가 곱한 수 만큼의 거리($n$)까지를 고려한다(?)는 의미로 알고있는데, 자세한 내용은 graph theory를 자세히 공부한 적이 없어서 아직은 잘 모르겠다😥
Implementation
상단 repo link 참고
tf-v1이라 코드 해석 및 실행이 많이 힘들었던 기억이 새록새록 난다.
Related Work
Graph-based Semi-Supervised Learning
크게 2가지 접근법이 존재.
- 명시적으로 graph Laplacian regularization 형태를 사용하는 방법
: label propagation [Zhu et al., 2003], manifold regularization [Belkin et al., 2006], deep semi-supervised embedding [Weston et al., 2012] - graph embedding에 기반한 방법
: DeepWalk [Perozzi et al., 2014], LINE [Tang et al., 2015], node2vec [Grover & Leskovec, 2016], Planetoid [Yang et al., 2016]
graph embedding 방법 중 DeepWalk, LINE, node2vec은 모두 random walk를 생성한 후 semi-supervised learning을 진행하는 2-step pipeline이 필요하여 두 step이 분리되어 최적화가 되어야 하지만, Planetoid는 embedding 학습 중 label 정보가 주입되어 그런 별도의 작업이 필요하지 않다.
Neural Networks on Graphs
Gori et al. (2005)에 의해 graph에 동작하는 neural network가 처음 소개되었고, Scarselli et al. (2009)에 의해 RNN을 이용한 방법이 소개되었다.
RNN을 이용한 방법엔 여러 제약점이 존재했고, 이를 해결하기 위해 Li et al. (2016)에 의해 개선된 연구를 소개되었고, Duvenaud et al. (2015)에 의해 graph-level classification task에 convolution-like propagation rule이 소개되었다.
하지만 이 방법들은 node degree에 특정된 weight matrix가 필요했고, 이는 large graph에는 적용되기 힘든 문제가 있었다.
앞선 연구들과는 다르게 본 논문에서는 layer 당 1개의 weight matrix를 가지며, $A$를 적절하게 정규화하여 여러 node마다 다른 degree를 다룰 수 있도록 하였다.
spectral graph convolutional neural network는 Bruna et al. (2014)에 의해 소개가 되었고, Defferrad et al. (2016)가 fast localized convolution을 이용해 앞선 연구를 개선하였다.
본 연구에서는 조금 더 큰 규모의 network(graph)에서 node classification을 하는 방법을 고안하였고, 기존 framewortk에 몇가지 단순화(simplification)를 진행하여 large scale network(graph)에서 더 나은 scability와 classification performance를 달성할 수 있었다.
(단순히 related work 소개 + 우리 paper가 이래서 더 좋다~ 하는 내용들.)
Experiments
Datasets
Planetoid [Yang et al., 2016]에서 사용한 Citeseer, Cora, Pubmed, NELL을 사용.
Citation, Cora, Pubmed와 같은 Citation network에 대해선 citation link를 undirected edge로 판단하여 binary, symmetric adjacency matrix $A$를 생성하였다.
Knowledge graph인 NELL에 대해선 $(e_1, r, e_2)$와 같은 entity relation을 $(e_1, r_1), \ (e_2, r_2)$와 같이 분리하였고, 모든 relation node마다 one-hot representaion을 할당하였으며, Citation network와 마찬가지로 binary, symmetric adjacency matrix $A$를 생성하였다. (두 node 사이에 1개 이상의 edge가 연결되어 있다면 1, 아니라면 0)
Experimental Setup
- 2-layer GCN
- Planetoid [Yang et al., 2016]과 동일한 dataset split 진행
- 200 epoch
- Adam with learning rate 0.01
- early stopping with window size 10
- Glorot & Bengio weight initialization (Xavier initialization)
- input feature에 대해 row normalize 진행
- hidden layer size 32
Baselines
Planetoid [Yang et al., 2016]과 동일한 baseline 사용, 추가적으로 Planetoid와 비교 실험 진행.
Results
table에서 볼 수 있듯이, 기존 method들에 비해 significant한 성능 향상을 달성했다.
Planetoid와 제안한 GCN에 대해 wall-clock training time(실제 train에 소요된 시간)을 측정하였는데, 대부분의 경우 Planetoid에 비해 시간이 단축된 점을 확인할 수 있다.
특이하다고 느꼈던 점은 기존의 propagation 방법들에 대한 비교 실험도 진행한 것인데, 논문에서 제안했던 renormalization trick을 적용한 경우의 perfomance가 가장 좋은 결과를 보여주고 있다.
앞서 언급했었던 기존 방법(수식)들의 한계점을 결과로서 직접 보여주고자 했던 것이지 않았을까 라는 생각이 들었었다.
Discussion & Conclusion
graph Laplacian regularization에 기반한 방법은 edge가 단순히 node의 유사성(similarity)을 encode한다고 가정하기에 제한점이 많을 수 있다.
Skip-gram(embedding) based method에 기반한 방법은 최적화하기가 어려운 multi-step pipeline에 기반한다는 점에서 한계점이 존재한다.
본 논문에서 제안한 방법은 두 가지의 한계점을 모두 극복할 수 있으며, 각 layer에서 이웃 node들의 feature information의 propagation을 통해 classification performance를 높일 수 있다.
하지만 본 논문에서는 edge feature를 고려하지 않았고, undirected graph만을 고려하였다.
또한 암묵적으로 locality ($K$개의 layer를 가진 GCN에서 $K^{th}$ 차수의 이웃에 의존적)를 가정하였고, 몇몇 데이터 셋에 있어서는 self-connection과 이웃 node와의 edge에 대한 가중치를 조절할 수 있는 파라미터 $\lambda$를 이용해 $\tilde{A} = A + \lambda I_N$와 같이 이용하는 것이 바람직할 수 도 있다.
결과적으로 graph 데이터에 대해 semi-supervised classification을 수행하는 novel approach를 소개하였고, 소개하였던 first order approximation of spectral convolution에 기반한 layer-wise propagation rule이 효과적임을 보여주었다.
실제로 GCN code를 실행해보면 상당히 빠르게 동작하는 것을 볼 수 있다.
Graph Neural Network 연구를 시작할 때 Jure Leskovec 교수님의 강의 CS224W, pytorch geometric 공식 tutorial, DeepFindr 채널 등 인터넷에 공개된 좋은 자료들의 도움을 정말 많이 받았었다.
22년 당시 review 후에 작성하였던 슬라이드도 함께 첨부하였다.
E.O.D.