연구를 하면서 머신러닝에 사용되는 Graph에 관해 알아둘 필요가 있어, 관련 기초 내용을 알차게 다루는 Stanford CS224W 강의를 수강하고, 내용을 정리하려 한다.
유튜브 강의 링크는 다음과 같다.
https://www.youtube.com/playlist?list=PLoROMvodv4rPLKxIpqhjhPgdQy7imNkDn
Stanford CS224W: Machine Learning with Graphs
This course covers important research on the structure and analysis of such large social and information networks and on models and algorithms that abstract ...
www.youtube.com
목차
이전 포스팅에서 GNN의 목적과 핵심 과정을 살펴보았다.
https://jjuke-brain.tistory.com/entry/Graph-Neural-Networks-1-Deep-Learning-for-Graphs-GCN-GraphSAGE
Graph Neural Networks (1) - Deep Learning for Graphs, Message and Aggregation
연구를 하면서 머신러닝에 사용되는 Graph에 관해 알아둘 필요가 있어, 관련 기초 내용을 알차게 다루는 Stanford CS224W 강의를 수강하고, 내용을 정리하려 한다. 유튜브 강의 링크는 다음과 같다. htt
jjuke-brain.tistory.com
간단히 복습해보자.
Deep graph encoder는 graph를 입력으로 받아 graph neural network 여러 layer를 거쳐 node, 혹은 (sub)graph의 embedding을 출력해준다.
GNN의 한 layer에서는 target node의 이웃 노드들이 computation graph를 결정한다는 아이디어를 활용하여 이웃 노드의 information(message)을 계산하고, 이를 aggregation하여 node feature를 만들어낸다.
이번에는 이를 통해 전반적으로 Graph Neural Network를 이해해보고, 여러 classical한 모델들을 살펴보자.
General GNN Framework
GNN이 동작하는 전반적인 과정은 위와 같다.
(1) Message and (2) Aggregation
이전 포스팅에서 자세히 다루었던, GNN의 single layer를 정의하는 과정이다.
Single layer에서 message 계산을 어떻게 하느냐, aggregation을 어떤 방식으로 하는가에 따라 GCN, GraphSAGE, GAT 등의 GNN architecture가 정해진다.
(3) Layer Connectivity
GNN layer를 어떻게 쌓을 것인가에 대한 과정이다.
이 과정에서 skip connection 등의 trick을 사용하여 network의 robustness를 향상시킬 수 있다.
(4) Graph Augmentation
GNN의 input으로 들어오는 graph는 target node에 따라 달라지기 때문에 computation graph와 다르다.
따라서 이 과정에서 graph feature augmentation, graph structure augmentation을 적용한다.
(5) Learning Objective
GNN을 어떻게 train할 것인지를 정한다.
이 부분도 이전 포스팅에서 간단히 다루었다. (Loss function 설정 관점)
Supervised/Unsupervised objective와 node/edge/graph level objective를 설정한다.
이렇게 GNN이 동작하는 전반적인 과정을 순서대로 자세히 알아보자.
Single GNN Layer
GNN layer의 idea는 여러 vector의 set(이웃 노드의 embedding set)을 하나의 vector(node feature)로 압축하는 것이다.
동작 과정은 두 step으로 이루어진다.
- Message Computation
- Aggregation
Message Computation
Message의 계산은 다음과 같은 message function을 통해 이루어진다.
\( \mathbf{m}_u^{(l)} = \text{MSG}^{(l)} \left( \mathbf{h}_u^{(l-1)} \right) \)
- \(\mathbf{h}_u^{(l-1)}\) : 이전 layer의 결과인 node \(u\)의 embedding
- \(\mathbf{m}_u^{(l)}\) : 현재 layer에서 계산된 node \(u\)의 message
각 노드별로 message를 만들 것이고, 이를 다른 노드에 전달한다.
예를 들어, 간단히 linear layer인 경우, node feature를 weight matrix \(\mathbf{W}^{(l)}\)와 곱하여 다음과 같이 나타낼 수 있다.
\( \mathbf{m}_u^{(l)} = \mathbf{W}^{(l)} \mathbf{h}_u^{(l-1)} \)
Message Aggregation
이후에 target node의 embedding을 생성하기 위해 이웃 노드의 message를 종합(aggregate)한다.
\( \mathbf{h}_v^{(l)} = \text{AGG}^{(l)} \left( \left\{ \mathbf{m}_u^{(l)}, u \in N(v) \right\} \right) \)
Aggregation function으로는 \(\text{Sum}(\cdot)\), \(\text{Mean}(\cdot)\), \(\text{Max}(\cdot)\) aggregator등을 사용할 수 있다. 예를 들어, Sum을 사용한다면,
\( \mathbf{h}_v^{(l)} = \text{Sum}\left( \left\{ \mathbf{m}_u^{(l)}, u \in N(v) \right\} \right) \)
하지만, 위와 같은 단순한 형태의 aggregation function은 node \(v\) 스스로의 정보를 포함하지 않는다. (\(\mathbf{h}_v^{(l)}\)의 계산에서 \(\mathbf{h}_v^{(l-1)}\) term이 빠져있다.)
따라서, 이를 해결하기 위해서 aggregation function에 \(\mathbf{h}_v^{(l-1)}\) term을 추가해준다.
1. Node \(v\) 스스로의 message를 계산한다. 이때, 이웃 노드의 message를 계산할 때와는 다른 weight matrix \(\mathbf{B}^{(l)}\)를 사용한다.
\( \mathbf{m}_v^{(l)} = \mathbf{B}^{(l)} \mathbf{h}_v^{(l-1)}\)
2. Aggregation function에서 이웃 노드의 embedding을 aggregation 해주는 term에 추가하여 node 자신의 message도 추가하여 연결해준다.
따라서 최종적으로 aggregation은 다음과 같은 수식으로 진행한다.
\( \mathbf{h}_v^{(l)} = \text{CONCAT}\left( \text{AGG} \left( \left\{ \mathbf{m}_u^{(l)}, u \in N(v) \right\} \right), \mathbf{m}_v^{(l)} \right) \)
- \(\text{AGG} \left( \left\{ \mathbf{m}_u^{(l)}, u \in N(v) \right\} \right)\) : 이웃 노드들의 embeddig에 대한 aggregation
- \(\mathbf{m}_v^{(l)}\) : target node 자신의 message
Single GNN Layer
Message computation이나 aggregation 시 activation function을 통해 nonlinearity를 부여한다.
Activation function은 \(\sigma(\cdot)\)로 표현하며, \(\text{ReLU}(\cdot)\), \(\text{Sigmoid}(\cdot)\) 등이 될 수 있다.
Classical GNN Layers
이제 GNN의 대표적인 모델인 GCN, GraphSAGE, GAT에서 message computation과 aggregation을 어떤 방식으로 하는지 자세히 알아보자.
Graph Convolutional Networks (GCN)
GCN은 이전 포스팅에서도 언급했듯이, 단순히 이웃 노드의 embedding 평균으로 aggregation을 진행한다.
\( \mathbf{h}_v^{(l)} = \sigma \left( \mathbf{W}^{(l)} \sum\limits_{u \in N(v)} \cfrac{\mathbf{h}_u^{(l-1)}}{\lvert N(v) \rvert} \right) \)
- \(\mathbf{W}^{(l)} \cfrac{\mathbf{h}_u^{(l-1)}}{\lvert N(v) \rvert}\) : Message computation (weight matrix를 summation 안으로 넣었을 때)
- 각 neighbor에 대해 target node의 degree로 normalize된 message를 계산한다.
- \(\mathbf{m}_u^{(l)} = \cfrac{1}{\lvert N(v) \rvert} \mathbf{W}^{(l)} \mathbf{h}_u^{(l-1)}\)
- \(\underset{u \in N(v)}{\sum}\left( \cdots \right)\) : Aggregation
- Nonlinearity까지 고려하면, 이웃 노드로부터의 message를 더한 후, activation function을 적용한다.
- \(\mathbf{h}_v^{(l)} = \sigma \left( \text{Sum} \left( \left\{ \mathbf{m}_u^{(l)}, u \in N(v) \right\} \right) \right)\)
GraphSAGE
GraphSAGE도 이전 포스팅에서 언급했는데, aggregation을 좀 더 일반화하고, target node 자신의 embedding도 concat하는 과정을 추가해준다.
\( \mathbf{h}_v^{(l)} = \sigma \left( \mathbf{W}^{(l)} \cdot \text{CONCAT} \left( \mathbf{h}_v^{(l-1)}, \text{AGG} \left( \left\{ \mathbf{h}_u^{(l-1)}, \forall u \in N(v) \right\} \right) \right) \right) \)
Message는 \(\text{AGG}(\cdot)\) 함수 내에서 계산되며, aggregation은 두 가지 step으로 나뉜다.
- 이웃 노드 aggregation
- \(\mathbf{h}_{N(v)}^{(l)} \leftarrow \text{AGG} \left( \left\{ \mathbf{h}_u^{(l-1)}, \forall u \in N(v) \right\} \right)\)
- Target node 자신까지 aggregation
- \( \mathbf{h}_v^{(l)} \leftarrow \sigma \left( \mathbf{W}^{(l)} \cdot \text{CONCAT} \left( \mathbf{h}_v^{(l-1)}, \mathbf{h}_{N(v)}^{(l)} \right) \right) \)
GraphSAGE에서 neighbor aggregation 과정에 사용 가능한 함수는 다음과 같다.
Mean
이웃 노드 embedding의 Weighted average를 취한다.
\( \text{AGG} = \sum\limits_{u \in N(v)} \cfrac{\mathbf{h}_u^{(l-1)}}{\lvert N(v) \rvert} \)
Pool
이웃 embedding vector들을 multi layer perceptron으로 transform하고, \(\text{Mean}(\cdot)\)이나 \(\text{Max}(\cdot)\) 등의 symmetric vector function을 적용한다.
\( \text{AGG} = \text{Mean} \left( \left\{ \text{MLP}\left( \mathbf{h}_u^{(l-1)} \right), \forall u \in N(v) \right\} \right) \)
이 경우, \(\text{MLP}\) 적용한 부분이 message computation, \(\text{Mean}\)을 적용한 부분이 aggregation이다.
LSTM
이웃 노드를 reshuffle하기 위해 LSTM을 적용한다.
\( \text{AGG} = \text{LSTM} \left( \left[ \mathbf{h}_u^{(l-1)}, \forall u \in \pi \left( N(v) \right) \right] \right) \)
순열\(\pi\)을 통해 reshuffle한 이웃 노드에 대해 aggregation(\(\text{LSTM}\))한다.
다음으로, L2 normalization을 적용한다. 이 부분은 이전 포스팅을 참조하자. (사실 위 내용도 이전 포스팅에서 한 번씩 언급한 내용이다.)
GAT
GAT는 graph에 attention network를 사용한 모델이다.
\( \mathbf{h}_v^{(l)} = \sigma \left( \sum\limits_{u \in N(v)} \alpha_{vu} \mathbf{W}^{(l)} \mathbf{h}_u^{(l-1)} \right) \)
- \(\alpha_{vu}\) : node \(u\)의 message가 node \(v\)로 전달될 때의 Weighting factor(attention weight, importance 개념)이다.
GCN이나 GraphSAGE에서는 이 값이 \(\cfrac{1}{\lvert N(v) \rvert}\)로 명시적으로 정해진다. (graph의 구조적인 특성 중 하나인 target node의 degree로 normalize함)
하지만, 이렇게 명시적으로 attention weight를 주게 되면 모든 neighbor node가 같은 importance를 갖게 된다.
따라서 GAT에서는 이웃 노드별로 중요도를 달리 준다.
Attention Weight \(\alpha\)
Attention의 개념은 neural network가 계산을 할 때, 데이터의 중요한 부분에 좀 더 computing power를 많이 쓰도록 하자는 개념이다.
데이터의 어떤 부분이 더 중요한가(attention weight를 어떻게 결정할 것인가)는 context에 따라 결정되고, training 과정에서 학습된다.
이 개념을 graph에 적용하기 위해서 각 노드의 embedding \(\mathbf{h}_v^{(l)}\)을 계산할 때 attention strategy를 따르도록 한다.
노드의 embedding은 그 이웃 노드의 message에 의해 결정되므로, embedding을 계산할 때 (implicit하게) 노드 각각에 서로 다른 weight를 부여한다.
먼저, node \(u, v\)의 message 쌍에 대해 Attention mechanism \(a\)를 사용하여 attention coefficients(energy) \(e_{vu}\)를 구한다.
\( e_{vu} = a \left( \mathbf{W}^{(l)} \mathbf{h}_u^{(l-1)}, \mathbf{W}^{(l)} \mathbf{h}_v^{(l-1)} \right) \)
- \(e_{vu}\) : node \(u\)의 message가 node \(v\)로 전달될 때의 importance
- 이전 layer에서의 두 node의 embedding으로 구한다.
최종 attention weight \(\alpha_{vu}\)를 구하기 위해 \(\mathbf{e}_{vu}\)에 softmax 함수를 적용하여 이웃 노드들에 대한 \(\alpha\) 값의 합이 1이 되도록 한다.
\( \alpha_{vu} = \cfrac{\text{exp}(e_{vu})}{\sum_{k \in N(v)} \text{exp}(e_{vk})} \)
이 attention weight를 사용하여 weighted sum을 하면 맨 위의 식을 얻게 된다.
예를 들어, 위 그림의 graph에서 target node \(A\)에 대한 embedding은 다음과 같이 계산한다.
\( \mathbf{h}_A^{(l)} = \sigma \left( \alpha_{AB} \mathbf{W}^{(l)} \mathbf{h}_B^{(l-1)} + \alpha_{AC} \mathbf{W}^{(l)} \mathbf{h}_C^{(l-1)} + \alpha_{AD} \mathbf{W}^{(l)} \mathbf{h}_D^{(l-1)} \right) \)
Attention Mechanism \(a\)
\(a\)를 무엇으로 설정하는지에 따라 다양한 GAT 모델이 있다.
가장 간단한 방법은 simple single-layer neural network를 사용하는 것이다. 이에 따라 \(a\)는 학습 가능한 parameter(linear layer에서의 weight)를 갖게 된다.
\( \begin{align*} e_{AB} &= a \left( \mathbf{W}^{(l)} \mathbf{h}_A^{(l-1)}, \mathbf{W}^{(l)} \mathbf{h}_B^{(l-1)} \right) \\ &= \text{Linear} \left( \text{Concat} \left( \mathbf{W}^{(l)} \mathbf{h}_A^{(l-1)}, \mathbf{W}^{(l)} \mathbf{h}_B^{(l-1)} \right) \right) \end{align*} \)
\(a\)의 parameter는 GNN에서의 parameter들(\(\mathbf{W}, \mathbf{B}\) 등)과 함께 학습(trained jointly)된다. 따라서 end-to-end로 학습이 가능하다.
Multi-head attention
Multi-head attention은 attention mechanism의 학습 과정을 안정화하기 위해 적용한다.
각 node 쌍에 대해 여러번의 attention score를 생성한다. 이때 parameter는 서로 다른 attention weight이다.
\( \mathbf{h}_v^{(l)}[1] = \sigma \left( \sum_{u \in N(v)} \alpha_{vu}^1 \mathbf{W}^{(l)} \mathbf{h}_u^{(l-1)} \right) \)
\( \mathbf{h}_v^{(l)}[2] = \sigma \left( \sum_{u \in N(v)} \alpha_{vu}^2 \mathbf{W}^{(l)} \mathbf{h}_u^{(l-1)} \right) \)
\( \mathbf{h}_v^{(l)}[3] = \sigma \left( \sum_{u \in N(v)} \alpha_{vu}^3 \mathbf{W}^{(l)} \mathbf{h}_u^{(l-1)} \right) \)
최종 output은 이들을 aggregate한다. (concat, sum 등 활용)
\( \mathbf{h}_v^{(l)} = \text{AGG} \left( \mathbf{h}_v^{(l)} [1], \mathbf{h}_v^{(l)} [2], \mathbf{h}_v^{(l)} [3] \right) \)
Benefits of Attention Mechanism
Attention을 적용했을 때의 주요 장점은 맨 처음 언급했다시피 각 이웃 노드에 서로 다른 importance 값(\(\alpha_{vu}\))을 부여할 수 있다는 점이다.
이외에도 다음과 같은 장점이 있다.
- Computationally efficient
- Attention coefficient 계산은 모든 edge에 대해 병렬로 계산할 수 있다.
- Aggregation 계산은 모든 node에 대해 병렬로 계산할 수 있다.
- Storage efficient
- Sparse matrix에 대한 연산은 많아봤자 \(O(V + E)\)만큼의 용량이 필요하다.
- 그래프의 size에 관계 없이 고정된 parameter 수를 갖는다.
- Localized
- 중요한 local network에 주의(attention)를 기울인다.
- Inductive capability
- Shared edge-wise mechanism으로, 전체 graph 구조에 의존하지 않는다.
이러한 장점 덕분에, cora citation net에서 GCN보다 높은 성능을 보였다. (당연히 MLP, DeepWalk 등의 방법보다 훨씬 높은 성능을 보인다.)
최근댓글