[DL] Graph Neural Networks

< 목차 > 

1. Graph 

• Graph의 구성 
• Graph Representation 
• Degree 
• Neighborhood Normalization 

2. Graph Neural Networks(GNN) 

• GNN Tasks 
• GNN Learning Process 
• GNN Variants 

---

1. Graph 

1) Graph의 구성 

Graph Data Structure는 Node(그래프 하나의 원소)와 Edge(노드들 간의 연결 관계)로 이루어져 있다. 

• Graph G = (V, E) 
  • V: nodes, E: edges, weight(edge property) 
• Graph Data: Data 간의 Relation이 포함되어 있는 Data임. node들 간의 관련성을 표현하는 것이 매우 중요함 

Graph는 Directed Graph와 Undirected Graph로 구분됨 

• Directed Graph: 노드 간 Sequence(or 방향성)이 있는 경우
• Undirected Graph: 노드 간 Sequence(or 방향성)가 없는 경우, node간의 연결만 표현

 

 

2) Graph Representation 

• Graph는 보통 Node-Feature Matrix와 Adjacency Matrix로 표현됨 
• Node-Feature Matrix: node의 속성을 표현하는 matrix
• Adjacency Matrix: node들 간의 관계를 나타낸 matrix (선의 연결 유무를 matrix화 함) 
  • Undirected Graph: N by N square matrix, 대칭 형태
  • Directed Graph: N by N matrix, 비대칭 형태 

Adjacency Matrix 예시 (연결이 되어 있으면 1, 없으면 0)

 

3) Degree 

Degree는 그래프에서 노드가 몇 개의 노드와 연결되어 있는지 개수를 CountCount 한 것

 

4) Neighborhood Normalization

모든 node들은 동일한 개수의 edge를 가지고 있지 않음. 모든 node에 동일한 weight를 부여하기 위한 Normalize가 필요함. 따라서 Graph matrix에 Normalize를 수행함

 

 

2. Graph Neural Networks(GNN) 

1) GNN Tasks 

GNN은 아래의 3가지 방법으로 활용됨

• Node Level : node의 label을 prediction 하는 문제 
• Edge Level : node 사이의 관계를 prediction 하는 문제
• Graph Level : node, edge가 구성된 네트워크 전체를 학습하여 graph의 label을 prediction 하는 문제 

 

2) GNN Learning Process  

GNN의 layer에서는 node feature들이 graph structure를 반영하여 계속 업데이트 됨. Graph의 feature update 과정은 Aggregate, Combine, Readout 으로 구성됨

• Aggregate(=Message Passing) : 타겟 노드의 이웃 노드들의 k-1 시점의 hidden state를 결합하는 것
• Combine(=Update) : k-1 시점의 타겟 노드의 hidden state와 aggregated information(이웃 노드들의 정보)을 사용하여 k시점 target node의 hidden state를 update하는 것 
• Readout : k 시점의 모든 node들의 hidden state를 결합하여 전체 Graph의 hidden state를 생성하는 것 (Graph level classification 에 사용됨) 

GNN 학습 과정

(참고) GNN Notation

GNN의 Aggregate-Combine-Readout 과정은 아래와 같이 진행됨 

• Aggregate : 현재 target 노드의 이웃 노드들의 k-1시점의 hidden state를 결합함. 이것이 target node의 aggregated information이 됨. 인접 노드들의 특성을 target node의 feature로 활용한다는 의미임. 

GNN: Aggregate

• Combine: 이웃 노드들의 정보(aggregated information)과 타겟 노드의 정보(k-1 시점 까지)를 사용하여 k시점(현재) 타겟 노드의 hidden state를 update하는 것. 즉, "(k-1시점 자기자신 정보) + (k-1시점 이웃 노드들의 정보) = k 시점 자기자신의 정보" 가 되는 것. 

GNN: Combine

• Readout : k시점의 모든 node들의 hidden state를 결합하여 graph 전체의 hidden state를 생성하는 것. Graph level의 학습을 진행할 때만 사용됨 

GNN: Readout

 

3) GNN Variants (참고)

GNN은 Aggregate와 Combine function의 정의에 따라 다양한 방식의 모델이 존재함

- GNN 

- GNN (Self-loop) 

- Graph Convolutional Networks (GCN)

- Gated Graph Neural Networks 

- GraphSAGE

• 여러 GNN Variant들이 나온 이유는 다음과 같은 문제들을 해결하기 위함임
  • Self-loop
  • Node degrees (GCN)
  • Node Importance (GraphSAGE)
  • Overfitting / Vanisihing gradient (GGNN) 
• 이러한 문제들을 Attention 해결 가능한, Graph+Attention 개념의 새로운 모델이 등장함 --> GAT(Graph Attention Networks) 

(GAT 설명은 다음 글)