주뇽's 저장소
6. Graph Neural Networks(2) CS224W: Machine Learning with Graphs 정리 본문
https://web.stanford.edu/class/cs224w
목차
1. 그래프 신경망(GNN) - Part 2
- GNN Layer
2. GNN Layer 종류
- GCN
- Graph SAGE
- GAT
👉 이전 내용
노드임베딩 : 실제 그래프에서 2개의 노드 U,V를 임베딩 공간 Z로 가장 잘 매핑할 수 있는 인코더를 찾는 것!
그렇다면 어떻게 가장 잘 설명할 수 있는 인코더를 만들까?
-> 그래프 머신러닝 Depp Graph Encoders를 이용하여 인코더를 학습!!!
Input : Graph
Ouput : 노드뿐 아니라 서브그래프, 그래프도 임베딩 가능!
👉 1. 그래프 신경망(GNN) - Part 2
1. GNN Layer
GNN의 기본 레이어 : Message 함수 + Aggregation 함수
GraphSAGE, GCN, GAT의 차이는 어떤 메시지 함수와 집계 함수를 쓰는지에 대한 차이일뿐이다.
1. Message 함수
- Message 함수: 선형변환 등으로 노드 메시지 생성
간단한 선형 레이어 = W행렬과 이전 레이어의 특성을 곱함
2. Aggregation 함수
- Aggregation 함수: 이웃 메시지 요약(평균, 합, 최대 등) 다양한 딥러닝 모듈 활용 가능
- Batch Normalization: 임베딩 정규화로 학습 안정화
- Dropout: 과적합 방지를 위한 임의 노드 제거
- Activation: 비선형성 추가 (ReLU, Sigmoid 등)
- 적절한 모듈 조합으로 문제에 최적화된 GNN Layer 설계
A노드와 이웃노드 3개의 B, C, D 메시지를 평균, 합, 최대 등을 이용하여 요약한다(순서의 영향을 받지 않기 위해)
위와 같이 A노드를 업데이트 하는 과정에서 우리는 일반적으로 "자기 자신을 표현하는데 자기자신에 대한 정보를 제외하고 이웃정보만을 사용하는건 좋지 않은 방법이지 않을까?" 라는 생각을 가지게 된다! 이러한 문제점을 해결하기 위해서 2개의 가중치 행렬을 통해 메시지를 집계한다!
문제점
- 위와 같은 방식으로 메시지를 집계 한다면 자기 자신 A노드에 대한 정보는 유실될 수 있다.
해결방법
- 자기자신에 대한 정보를 업데이트 하는 행렬 B와 이웃 노드에 대한 정보를 업데이트하는 행렬 W를 통해 각각 업데이트를 진행한다.
- 이후 이웃 메시지와 자기 자신 메시지를 합친다.
👉 GNN Layer 종류
기존의 GCN 레이어의 모습은 아래와 같다.
- 이웃 노드들의 임베딩을 먼저 평균 내고 (∑_{𝑢∈𝑁(𝑣)} 𝐡_𝑢^((𝑙−1))/|𝑁(𝑣)|), 그 결과에 가중치 행렬 𝐖^((𝑙))를 곱한다.
- 즉, 집계된 메시지에 한 번의 선형 변환을 수행하는 셈이다.
- 모든 이웃 노드들의 임베딩이 동일한 가중치 행렬에 의해 변환된다.
1. GCN
이전 GCN 레이어 같은 경우 특정 노드의 특징 = 자신과 연결된 모든 노드들의 특징들의 합 * 행렬 W의 곱으로 표현했다.
위와 같은 GNN의 기본 레이어에 어떻게 메시지 전파와 집계 함수를 적용 할 수 있을까?
- 각 이웃 노드의 임베딩에 가중치 행렬을 곱한 후 (𝐖^((𝑙))𝐡_𝑢^((𝑙−1))), 그 결과를 모두 더하고 평균을 낸다.
- 즉, 각 이웃 노드의 메시지를 개별적으로 변환한 후 집계하는 것
이러한 차이로 인한 두 가지 효과:
1. 첫번째 수식은 모든 메시지를 합친 후 한 번의 행렬 곱셈을 수행하기 때문에 계산 효율성 측면에서 유리할 수 있다.
2. 두번째 수식은 각 메시지를 개별적으로 변환하므로, 이웃 노드의 정보를 보다 세밀하게 구분하여 집계할 수 있다. 이는 노드 임베딩의 표현력을 높일 수 있다.
다만 실제로는 대부분의 경우 두 수식의 성능 차이가 크지 않다고 알려져 있다. 따라서 GCN 논문에서는 계산 효율성이 더 좋은 첫번째 수식을 기본으로 사용하고 있다. 하지만 문제의 특성에 따라 두번째 수식이 더 적합할 수도 있으므로, 상황에 맞게 적절한 수식을 선택하는 것이 좋다.
2. Graph SAGE
Graph SAGE는 GCN을 변형한 방식이다. GCN의 경우 자기 자신에 대한 정보는 없지만 Graph SAGE는 자신의 이전 임베딩도 포함한다. 이 때 집계 함수는 Mean, Pool, LSTM 등을 사용할 수 있다.
노드 v의 이웃 노드의 임베딩 {h_u^(l-1)}를 AGG 함수로 집계하고, 노드 v 자신의 이전 층 임베딩 h_v^(l-1)과 연결(CONCAT)한 후 변환 행렬 W^(l)을 곱하고 활성화 함수를 취한다.
예시: 노드 A의 임베딩을 위해 우선 이웃 B, C, D 임베딩을 평균(Mean) 함수로 집계한다. 그 다음 집계한 값과 노드 A의 이전 임베딩을 연결하여 변환 및 비선형함수를 거쳐 새로운 노드 A의 임베딩을 얻는다.
이 때 사용하는 집계 함수는 자유롭게 선택이 가능하며 해당 강의 자료에서는 크게 3가지를 제안한다.(Mean, Pool, LSTM)
1. Mean 집계 함수:
- 설명: 노드 𝑣의 모든 이웃 노드 𝑢의 임베딩 𝐡_𝑢^((𝑙−1))을 단순히 더하고 이웃 수로 나눠 평균을 계산한다.
- 예시: 노드 A의 이웃이 B, C, D라면, 이들의 임베딩을 모두 더하고 3으로 나누어 평균 임베딩을 계산한다:
(𝐡_𝐵^((𝑙−1)) + 𝐡_𝐶^((𝑙−1)) + 𝐡_𝐷^((𝑙−1))) / 3
2. Pool 집계 함수:
- 설명: 먼저 각 이웃 노드 𝑢의 임베딩 𝐡_𝑢^((𝑙−1))에 MLP(Multi-Layer Perceptron)를 적용하여 변환한다. 그 후, 변환된 이웃 임베딩들에 대해 MAX 연산을 수행하여 가장 큰 값을 선택한다. 이는 가장 중요한 이웃의 정보를 강조하는 효과가 있다.
- 예시: 노드 A의 이웃 B, C, D의 임베딩에 각각 MLP를 적용한 결과가 [0.1, 0.5, 0.3]이라면, MAX 연산을 통해 0.5를 선택한다. 이 값이 노드 A의 집계된 이웃 정보가 된다.
3. LSTM 집계 함수:
- 설명: 노드 𝑣의 이웃 노드 집합 𝑁(𝑣)를 무작위로 섞은 순열 𝜋(𝑁(𝑣))를 생성한다. 이 순열에 따라 나열된 이웃 노드의 임베딩을 순서대로 LSTM에 입력하여 마지막 은닉 상태를 출력한다. 이는 이웃 노드의 순서 정보를 고려하면서 이웃 정보를 집계하는 방법이다.
- 예시: 노드 A의 이웃 B, C, D를 무작위로 섞어 [D, B, C] 순서가 되었다고 가정
이 때, 𝐡_𝐷^((𝑙−1)), 𝐡_𝐵^((𝑙−1)), 𝐡_𝐶^((𝑙−1))를 차례대로 LSTM에 입력하고, 마지막 은닉 상태를 노드 A의 집계된 이웃 정보로 사용한다.
이처럼 GraphSAGE는 다양한 집계 함수를 통해 이웃 노드의 정보를 유연하게 집계할 수 있습니다. 각 집계 함수는 이웃 노드의 정보를 요약하는 서로 다른 방식을 제공하며, 이를 통해 노드 임베딩의 표현력을 높일 수 있다. 특히, Pool과 LSTM 집계 함수는 이웃 노드 간의 중요도 차이와 순서 정보를 고려할 수 있어, 보다 풍부한 이웃 정보를 집계할 수 있다.
3. GAT(Graph Attention Network)
모든 노드의 중요도를 1로 설정했던 GCN과 Graph SAGE와는 다르게 GAT는 이웃 노드의 중요도를 고려하여 가중치를 부여하는 Attention 메커니즘을 사용하여 메시지를 집계하는 GNN 모델이다. 이를 위해 GAT는 다음과 같은 과정을 거친다.
1. Attention 계수 계산:
- 설명: 노드 𝑣와 그 이웃 노드 𝑢 사이의 Attention 계수 𝑒_𝑣𝑢를 계산한다. 이는 노드 𝑢의 임베딩 𝐡_𝑢^((𝑙−1))과 노드 𝑣의 임베딩 𝐡_𝑣^((𝑙−1))을 가중치 행렬 𝐖^((𝑙))로 변환한 후, Attention 함수 𝑎에 입력하여 계산된다. 이 계수는 노드 𝑢가 노드 𝑣에 대해 갖는 중요도를 나타낸다.
- 예시: 노드 A와 그 이웃 B, C, D에 대해 Attention 계수를 계산한다고 가정
먼저 각 노드의 임베딩에 가중치 행렬을 곱한 후, Attention 함수에 입력하여 𝑒_𝐴𝐵, 𝑒_𝐴𝐶, 𝑒_𝐴𝐷를 얻는다. 이 값들은 각각 B, C, D 노드가 A에 대해 갖는 중요도를 나타낸다.
2. Attention 가중치 계산:
- 설명: Attention 계수를 Softmax 함수를 사용하여 정규화함으로써 Attention 가중치 𝛼_𝑣𝑢를 계산한다. 이 과정을 통해 모든 이웃 노드에 대한 Attention 가중치의 합이 1이 되도록 조정한다. 이 값들은 각 이웃 노드가 노드 A의 임베딩 계산에 기여하는 비율을 나타낸다.
3. 임베딩 계산:
- 설명: 각 이웃 노드의 임베딩에 해당 Attention 가중치를 곱하고, 이를 모두 더한 후 활성화 함수 𝜎를 적용하여 노드 𝑣의 새로운 임베딩 𝐡_𝑣^((𝑙))을 계산한다. 즉, 각 이웃의 임베딩에 Attention 가중치를 곱한 값들을 더하고 활성화 함수를 적용한 것이다.
여기까지 따라온다면 당연하게 생각이 드는 질문은 다음과 같다.
Q : 그렇다면 에너지(e)를 계산하는 a는 어떻게 정의해야하는가..?
일반적으로는 선형레이어를 이용해서 에너지(e)를 계산한다.
즉, 이전 레이어의 임베딩 벡터 2개를 결합한 후 선형레이러를 통과해서 에너지를 계산한다.
위와 같은 방식으로 학습을 하면 가중치 행렬을 Attention 가중치를 학습할 때도 공유하며 End to End 학습을 하게 된다.
노드의 중요성과 노드안에 들어있는 메시지까지 함께 학습을 한다는것은 상당히 어려운 작업이 될 수 있다. 따라서 최적의 파라메터를 학습하기 상당히 까다롭다라는 것을 느낄 수있다. 이를 해결하기 위해 Attention 개념을 Multi-head Attention으로 확장해서 사용할 수 있다.
Multi-head Attention
Multi-head Attention은 여러 개의 Attention 메커니즘을 병렬로 적용하고, 그 결과를 연결(Concatenation)하거나 평균내어 사용한다. 이를 통해 다양한 관점에서 이웃 노드의 중요도를 평가할 수 있으며, 모델의 표현력을 높일 수 있다.
이 과정에서 다양한 관점에서 이웃 노드의 중요도를 평가해야 하므로 서로 다른 함수 a를 갖게 된다.
위와 같이 동일한 V노드와 연결된 U노드에 대한 임베딩 값을 갱신할 때 서로 다른 3개의 관점에서 중요도를 계산한다. 이 때 초기 파라메터는 각각 랜덤하게 초기화한다.
📝 정리
- GNN Layer
- GNN의 기본 레이어는 Message 함수와 Aggregation 함수로 구성됨
- GraphSAGE, GCN, GAT의 차이는 메시지 함수와 집계 함수를 어떻게 사용하는지에 따라 결정됨
- GNN Layer 종류
- GCN:
- 이웃 노드들의 임베딩을 평균내고 가중치 행렬을 곱하는 방식
- 모든 이웃 노드들의 임베딩이 동일한 가중치 행렬에 의해 변환됨
- GraphSAGE:
- GCN을 변형한 방식으로, 자신의 이전 임베딩도 포함
- 집계 함수로 Mean, Pool, LSTM 등을 사용 가능
- 다양한 집계 함수를 통해 이웃 노드 정보를 유연하게 집계하여 노드 임베딩의 표현력을 높임
- GAT(Graph Attention Network):
- 이웃 노드의 중요도를 고려하여 가중치를 부여하는 Attention 메커니즘 사용
- Attention 계수 계산 -> Attention 가중치 계산 -> 임베딩 계산의 과정을 거침
- Multi-head Attention을 통해 다양한 관점에서 이웃 노드의 중요도를 평가하고 모델의 표현력을 높임
- GCN:
'GNN > CS224' 카테고리의 다른 글
| 7. 다층 GNN 레이어 CS224W: Machine Learning with Graphs 정리 (0) | 2024.04.11 |
|---|---|
| 5. Graph Neural Networks(1) CS224W: Machine Learning with Graphs 정리 (4) | 2024.03.26 |
| 4. 노드 임베딩 CS224W: Machine Learning with Graphs 정리 (0) | 2024.03.19 |
