Graph Neural Networks
Knowledge graph, Molecular graph, Social graph 등 graph 구조를 통해서만 표현될 수 있는 데이터들을 활용하기 위해 Graph Neural Networks(GNN)의 사용이 점점 증가하고 있는 추세이다. Graph 데이터를 활용하는 태스크들은 아래와 같다.
- Node classification : 주어진 노드의 타입을 예측
- Link Prediction : 특정 노드들이 연결될지 예측
- Community detection : 노드의 군집이 densely 연결되어있는지 확인
- Network similarity : 두개의 네트워크가 얼마나 비슷한지 확인
이러한 문제를 풀기위해 초기에는 Multi-hop Similarity, DeepWalk과 같은 Node 임베딩이 활용되었다. 하지만 NLP에서도 초창기에는 자주 활용되었던 Word2Vec, FastText와 같은 임베딩이 현재는 잘 활용되지 않고 RNN, Transformer과 같은 모델에서 supervised learning으로 학습되듯이 GNN이 본격적으로 등장하고 나서부터는 Node 임베딩이 잘 활용되지 않고 있다.
본 포스팅 글에서 설명할 GCN은 GNN 아키텍쳐 중에서도 가장 유명하며 이미지에서의 CNN과 유사한 장점들을 지니고 있다. 이미지에서 각 pixel들이 weight sharing 필터 연산을 통해 연산되며 Parallel Translation 문제를 방지할 수 있듯이, 그래프에서도 인접 노드들에 대한 local 정보를 동일한 weight로 연산되어 인접한 정보를 학습할 수 있다.
GCN(Graph Convolutional Networks)이 처음 제안된 논문에서는 semi-supervised learning 효과를 입증했다(Kipf, T. N., & Welling, M. 2016). 이 논문에서 제안한 GCN은 Adjacency Matrix를 활용하여 연결된 노드들의 feature를 연산하고 학습하는 방식으로 semi-supervised learning에 대한 성능을 높이고자 하였다. Citation network, Knowledge graph 데이터로 실험 결과, Label rate가 0.001~ 0.036임에도 불구하고 비교 SOTA 모델들 대비 월등한 분류 정확도를 보였다.
이러한 GCN 구조에 대해 'Semi-supervised classification with graph convolutional networks' 논문을 토대로 정리해보고자 한다. 또한 추후 NLP Task에도 적용하며 코드를 구현해볼 예정이다.
GCN Architecture
전체 수식은 아래와 같이 표현되며 그림과 같이 노드 feature와 weight matrix와의 연산을 기반으로 한다.
$H^{(l+1)}=\sigma(D̃^{-\frac{1}{2}}ÃD̃^{-\frac{1}{2}}H^{(l)}W^{(l)})$
Step 1 : Adjacency Matrix 정규화 $ D̃^{-\frac{1}{2}}ÃD̃^{-\frac{1}{2}} $
각 노드에 연결된 edge의 수에 따라 Adjacency Matrix를 Normalization → 연결이 많이 되어있는 노드는 연산을 거듭할수록 값이 커지고 연결이 적은 부분은 상대적으로 작아지기 때문에 추후 gradient 학습 시 연결이 적은부분은 학습이 안될 수 있다. 따라서 연결된 edge 수가 많을수록 더 작은 가중치가 부여되도록 정규화하는 작업이다.
✔️ 원래의 인접행렬은 self loop을 의미하는 diagonal 부분은 0으로 들어가지만 GCN에서 Conv Layer가 늘어남에 따라 자기 자신 노드와 연결된 노드들의 feature를 연결하여 계산하기 위해 self loop에도 1값을 부여한다. 즉 Ã = Adjacency matrix + Identity matrix 를 기준으로 한다. (각 노드의 degree를 나타내는 Degree matrix 도 동일)
Step 2 : Hidden State, Weight Matrix 곱 연산 $ H^{(l)}W^{(l)}$
각 노드의 hidden state와 weight matrix 곱을 통해 새로운 representation을 구하는 과정이다. 이 연산을 통해 산출된 값은 인접 노드들간의 Neighborhood Aggregation을 위해 활용된다.
Step 3 : 정규화된 adjancecy matrix와 새로운 representation 곱 연산
새롭게 정의된 representation을 기준으로 인접 행렬과의 곱을 통해 연결된 노드들의 정보를 취합하는 과정이다. 이후 최종적으로 Activation(ReLU)를 통해 비선형 학습을 한다.
이 과정까지의 연산을 행렬연산으로 표현하면 다음과 같이 표현할 수 있다. (activation 제외)
( n : node 수 / f : feature dim / d : # of convolution filter)
Step 4 : Readout
GCN 논문에서는 설명되지 않았지만, Graph 구조의 특성 상 노드의 순서에 따라 값의 변동이 생길 수 있는 Permutation Invariance 문제를 방지하기 위해 최종 output layer 이전에 readout 과정을 거친다. 대표적인 readout 방법으로는 MLP를 활용한 각 노드 Feature의 Node-wise summation이 있다. (CNN 의 FC layer와 유사한 개념)
✔️ Example
아래 예시는 2개의 layer를 쌓았을 때의 수식이며, 그림을 통해 이러한 연산을 거친 후 최종 output node값과 ground truth와의 loss를 구하는 것을 알 수 있다.
$Z=softmax(\widetilde{A} ReLU(\widetilde{A}XW_0)W_1)$
Reference
- Kipf, T. N., & Welling, M. (2016). Semi-supervised classification with graph convolutional networks. arXiv preprint arXiv:1609.02907.