[GCN] SEMI-SUPERVISED CLASSIFICATION WITH GRAPH CONVOLUTIONAL NETWORKS 논문 리뷰

 

안녕하세요˙ ͜ʟ˙

GCN을 소개하는 포스팅을 작성하게 된 정정지입니다 ⛄︎

 

 

제가 GCN을 소개하는 데 참고한 논문은

ICLR 2017에 게재된 SEMI-SUPERVISED CLASSIFICATION WITH GRAPH CONVOLUTIONAL NETWORKS입니다!

 

 

GRAPH CONVOLUTIONAL NETWORKS, GCN은 이름에서 알 수 있듯이

그래프 구조의 데이터에 컨볼루션 연산을 적용할 수 있도록 설계된 신경망의 한 종류입니다.

 

 

그렇다면 그래프의 구조는 어떻길래 그래프에 특화된 모델을 필요로 하는 걸까요?

위의 그림은 일반적인 그래프를 나타내고 있습니다.

그래프는 특정 개체를 나타내는 정점(vertex or node), 그리고 두 정점 사이를 잇는 간선(edge)으로 이루어져 있습니다.

 

node에는 각자의 특징 정보(feature)가, edge에는 방향성(ex. node $i\rightarrow j$)이나 두 정점 사이의 weight에 대한 정보가 포함될 수 있습니다.

 

예를 들어, 아래 그림과 같이 여러 지하철역 사이의 관계를 나타내는 그래프가 있을 때

 

 

각 정점은 특정 지하철역을, 정점의 특징 정보에는 지하철역의 노선이나 환승역 여부 등을 나타낼 수 있습니다

그리고 간선은 지하철만으로 두 역을 오갈 수 있는지 여부(그림은 임의로 제가 만든 거라 잘못된 부분이 있을 수 있습니다,,ㅎㅎ!), 또는 두 지하철역 사이의 거리를 weight 값으로 가질 수도 있습니다

 

 

참고로 그래프는 edge의 방향성 유무에 따라 undirected/directed graph, 가중치 유무에 따라 weighted/binary graph로 나뉘는데요. 이 논문에서는 undirected graph에 초점을 맞췄다는 것만 알고 넘어가시면 됩니다!

 

 

---

그래프에 대한 설명은 이 정도로 해두고

그럼 이제 논문의 내용에 맞추어 GCN에 대해 설명하겠습니다!

 

 

 논문 제목에서 알 수 있다시피

 이 논문은 GCN을 사용하여 semi-supervised classification을 하는 것이 목표입니다.

 

즉, label이 있는 node와 없는 node가 섞여 있는 한 그래프에서 node classification을 하게 됩니다.

 

 

기존의 graph-based semi-supervised learning task에서는 아래와 같이

explicit graph-based regularization term을 적용한 loss function을 사용했습니다.

 

$$\mathcal{L}=\mathcal{L}_0+\lambda\mathcal{L}_{reg},\quad with \quad \mathcal{L}_{reg}=\sum_{i,j}A_{ij}||f(X_i)-f(X_j)||^2=f(X)^T\Delta f(X) $$

 

여기서 $X_i$는 node $i$의 feature vector, $A$는 두 정점을 잇는 edge에 대한 정보, 즉 adjacency matrix입니다.

 

regularization term $\mathcal{L}_{reg}$를 좀 더 살펴보면

두 노드 i와 j의 edge 값 $A_{ij}$, 그리고 두 노드의 feature vector의 $f(·)$에 대한 차의 제곱으로 나타납니다.

 

즉, 위의 손실 함수는

'인접한 두 node들은 비슷한 feature vector를 가질 것이다'라는 가정을 전제로 하고 있습니다.

(이를 논문에서는 'label information is smoothed over the graph'라고 표현하는데 이는 이웃 노드와의 차이(variation)를 'smoothness'로 나타내는 것으로, 두 노드가 유사한 성질을 가지면 smooth하다고 할 수 있습니다.)

 

근데 이러한 전제는

edge가 두 노드 사이의 유사성 외에 추가적인 정보를 담고 있을 수 있다는 가능성을 배제하는 것이기 때문에

본 논문에서는 node feature 와 adjacency matrix를 모두 사용하는 신경망 모델을 통해 그래프 구조를 인코딩함으로써

위의 문제를 해결하고자 하였습니다.

 

 

Layer-wise propagation rule

---

우선 이 논문에서 제안하는 layer-wise propagation rule부터 알아보도록 합시다.

 

$l+1$번째 layer에서의 output $H^{(l+1)}$은 다음의 수식을 통해 계산됩니다.

 

$$H^{(l+1)}=\sigma(\tilde{D}^{-1/2}\tilde{A}\tilde{D}^{-1/2}H^{(l)}W^{(l)})$$

 

이 식은 어떻게 나왔을까요?

 

 

Spectral Graph Convolutions

---

graph signal $x\in \mathbb{R}^{N}$, filter $g_\theta=diag(\theta),\,\theta\in\mathbb{R}^{N}$에 대해

spectral convolution은 다음과 같이 정의됩니다.

$$g_\theta\star x=Ug_\theta U^Tx$$

 

$U$는 normalized graph Laplacian $L=I_N-D^{-1/2}AD^{-1/2}=U\Lambda^UT$의 eigenvector의 행렬입니다.

여기서 graph signal이라는 표현이 조금 생소할 수도 있는데 node의 feature vector라고 생각하면 됩니다

 

그렇다면 spectral convolution 은 무엇이고 normalized graph Laplacian은 무엇일까요?

그리고 우리가 아는 CNN의 컨볼루션과는 무슨 차이가 있을까요?

 

 

우리가 아는 CNN의 컨볼루션은 spatial convolution입니다.

CNN 연산 과정을 그래프에 대입하여 생각해 보면,

filter의 크기가 고정된 채로 현재 filter가 지나는 노드와 가깝게 연결된 이웃 노드들 한정으로 컨볼루션 연산을 합니다.

 

그런데 이는 고정된 이웃 노드에서만 정보를 받아 update 되기 때문에

그 외의 노드에서 오는 정보가 충분히 흘러들어올 수 있음에도 이를 활용할 수 없다는 단점이 존재합니다.

 

그래서 여러 노드로부터 받은 signal들을 여러 요소로 나누어 노드의 특징을 더 잘 표현하게끔 하는 것이 바로 spectral convolution입니다.

 

그러면 왜

spectral convolution에 graph Laplacian을 쓸까요?

 

위의 그림은 맨 왼쪽의 그래프 G에 대한 degree, adjacency, 그리고 laplacian matrix를 나타낸 것입니다.

 

Degree matrix는 각 노드에 연결된 edge(혹은 노드)의 수를 원소로 갖는 대각 행렬이고

Adjacency matrix는 두 노드 사이의 연결 유무를 나타내는 행렬이며 (그래프 G가 binary matrix일 때를 예시로 들었습니다)

Laplacian matrix는 $L=D-A$로 계산되는데,

Laplacian matrix도 adjacency matrix처럼 그래프 구조를 나타내는 하나의 방식이라고 생각하시면 됩니다.

 

 

Laplacian matrix는 symmetric 하기  때문에 항상 eigen decomposition이 가능하고, eigenvector matrix $U$에 대해

$UU^T=I$를 만족합니다.

그렇기 때문에 논문의 수식(3)처럼 normalized graph Laplacian을 통해 spectral convolution을 정의할 수 있습니다.

(이를 수식적으로 증명? 하는 과정을 생략한 부분이 있는데, 기회가 된다면 나중에 추가로 포스팅해 보겠습니다!)

 

그런데 위의  spectral convolution은 L에 대한 고윳값 분해를 하는 과정에서 연산 비용이 상당히 많이 소모되기 때문에

Chebyshev polynomial $T_k(x)=2xT_{k-1}(x)-T_{k-2}x$을 통해 필터 $g_\theta(\Lambda)$를 근사화하였습니다.

$$g_{\theta'}(\Lambda)\approx \sum_{k=0}^K \theta_k'T_k(\tilde{\Lambda})$$

이때 $\tilde{\Lambda}=\frac{2}{\lambda_{max}}\Lambda-I_N$

 

이를 convolution 연산에 대입하면 convolved signal은 다음과 같이 정의됩니다.

 

$$g_\theta'\star x \approx \sum_{k=0}^{K} \theta'_kT_k(\tilde{L})x$$

 

 

Layer-Wise Linear Model

---

K가 클수록 다양한 convolution filter를 사용할 수 있지만 그만큼 연산 복잡도와 오버피팅도 증가하기 때문에

작은 K와 많은 convolution layer를 통해 filter의 다양성은 높이고 연산 복잡도 및 오버피팅을 낮추고자 하였고,

본 논문에서는 K=1로 세팅하였습니다.

 

 

$\lambda_{max} \approx 2$일 때 위의 근사화된 convolved signal은 다음과 같은 수식이 됩니다.

$$g_\theta'\star x \approx \theta(I_N+D^{-1/2}AD^{-1/2})x$$

 

이때 $I_N+D^{-1/2}AD^{1/2}$가 [0, 2]의 값이기 때문에 반복적으로 연산을 수행하면 기울기 소실/폭발 문제가 발생하게 되고

본 논문에서는 renormalization trick을 통해 최종적으로 위에서 언급했던 layer-wise propagation rule을 제안하였습니다.

 

signal $X \in \mathbb{R}^{N\times C}$, filter $F$에 대해

 $$Z = \tilde{D}^{-1/2}\tilde{A}\tilde{D}^{-1/2}X\Theta,$$

 

 

 

SEMI-SUPERVISED NODE CLASSIFICATION

---

 

 

위의 그림은 GCN의 구조를 나타낸 것으로,

그래프 구조(연결 상태)는 유지한 채로 node feature vector만 변하는 것을 알 수 있습니다.

 

 

node $i$의 output $Z_i$는 $\hat{A} = \tilde{D}^{-1/2}\tilde{A}\tilde{D}^{-1/2}$ 에 대해 다음과 같이 계산됩니다.

 

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

여기서의 adjacency matrix A는 이 포스팅 초입에서도 언급했듯이 undirected graph의 인접 행렬을 뜻합니다.

 

loss function은 label이 있는 데이터에 대해 cross-entropy를 사용했습니다. ($\mathcal{y}_L$: label 있는 노드들의 indices)

$$\mathcal{L}=-\sum_{l\in\mathcal{y}_L}\sum_{f=1}^F Y_{lf}lnZ_{lf}$$

 

 

이 논문에서 성능 검증을 위해 사용한 데이터셋은 총 4개로,

documents와 그들의 citation link로 이루어진 citation network datasets Citeseer, Cora, Pubmed

그리고 knowledge graph로부터 추출된 bipartite graph인 NELL 입니다.

 

각 데이터셋에 대한 분류 성능을 선행 연구와 비교한 결과

 

 

정확도 측면에서도 state-of-the-art 성능을 달성했을 뿐만 아니라,

wall-clock training time도 선행연구에서 제안한 Planetoid 대비 대부분의 경우에 빠른 것을 볼 수 있습니다.

 

 

 

또한, 앞서 spectral convolution에서 연산 비용 및 오버피팅 감소를 위해 필터의 근사화, small K 사용 등의 과정을 거쳐

최종적으로 Renormalization trick 구조를 갖추게 되었는데요

 

각 플로우에서의 모델의 성능을 평가한 결과

이 논문에서 최종적으로 제안한 것이 가장 성능이 좋은 것을 볼 수 있습니다.

근사화를 통해 성능의 하락 없이 연산량을 줄인 것이죠 !

 

 

결론적으로

GCN은 그래프 구조의 데이터에 곧바로 적용할 수 있는 신경망 모델로써

그래프의 정보를 최대한 활용하여 분류 성능을 높이고자 제안되었으며, 이는 선행 연구와의 비교를 통해 증명되었습니다.

 

그러나

데이터의 크기와 그래프의 밀집도에 따라 요구되는 메모리가 커지기 때문에 추가적인 근사화가 필요하며,

이 논문에서는 undirected graph를 중점으로 다뤘기 때문에 directed graph에 대한 사용이 가능한지에 관한 추가 실험의 필요성을 제기하였습니다.

 

 

그래프 데이터는 담을 수 있는 정보가 많고 실생활에 그래프로 나타낼 수 있는 데이터가 많기 때문에

그래프 기반 신경망 모델의 연구가 활발히 진행되고 있습니다.

 

이러한 흐름에서 GCN은 그래프 데이터의 정보를 최대한 활용하면서 높은 성능&비교적 낮은 연산량을 위해 고안된 모델로, GNN 모델 연구의 기반이 되고 있다고 해도 과언이 아닙니다 ٩(•̤̀ᵕ•̤́๑)૭✧

 

 

 

그럼 여기서 GCN 논문 리뷰를 마치도록 하겠습니다!

감사합니다 (*ˊᵕˋ*)ﾉ

 

 

P.S. 업로드가 많이 늦어진 점 죄송합니다,,,ㅠㅠ!

 

 

References

https://ralasun.github.io/deep%20learning/2021/02/15/gcn/

https://harryjo97.github.io/theory/Graph-Convoloution-and-Spectral-Filtering/

https://greeksharifa.github.io/machine_learning/2021/08/14/GFT/