[CS224W] 9. Theory of Graph Neural Networks

GNN은 (1) Node의 Local Neighborhood로부터 (2) NeuralNet으로 정보를 Aggregation해 Embedding을 만드는 것

✔️ Main Topic

• GNN은 Node, Graph Structure을 어떻게 구별하는가.
• Maximally expressive GNN model : 표현력을 어디서 극대화할 수 있을까.

✔️ Many GNN Models

각 모델마다 다른 Propagation, Aggregation, Transfomation 방법론을 가지고 있다.

GCN(Mean-Pooling)

• Element-Wise Mean Pooling으로 Aggregation(이웃들의 정보 수집) 한뒤, Linear(선형변환) + Relu를 적용한다.
  

GraphSAGE(Max-Pooling)

• Element-Wise Max Pooling으로 Aggregation 한뒤, MLP로 모아진 정보를 가공.
  

🔨 Local Neighborhood Structure

• 노드의 변수를 색으로 표현해보자. 즉, 동일한 색을 가진 노드는 같은 변수를 가진다.
  위 같은 그래프 구조에서 모든 노드가 동일한 변수를 가진다. 이 경우 local neighborhood structure를 이용해 각 노드를 구분해야 한다.

1. 1-hop Degree를 이용하면 3,5번 node는 구분이 가능하다.
   
2. 2-hop Degree까지 늘리면 4번까지 구분이 가능하지만, 1번과 2번 노드는 대칭구조이기에 hop를 늘려도 구분할 수 없게된다.
   

• 입력값으로 주어지는 그래프의 각 노드가 임의의 인코더를 통과하여 임베딩 공간에 위치하는 벡터로 바뀌는 과정.
• 이 과정을 통해 그래프에서 유사한 노드들이 임베딩 공간에서도 근처에 있도록 맵핑한다.

🔨 Computational Graph

• GNN은 각 Layer에서 이웃의 임베딩을 aggregate한다.
• GNN의 node embedding은 이웃구조로 부터 정의된 Computational Graph로 부터 생성된다.
• Computational Graph는 각 node의 Rooted Subtree Structure에 의해 결정된다.
  

  ✔️표현력이 좋은 GNN

  • 다른 트리 구조를 가지는 노드에 대해 항상 다르게 임베딩하는 것을 의미한다
  • subtree를 임베딩으로 일대일대응(Injective)시킨다
  • 다른 계산그래프에 대해 각각 다른 임베딩 벡터를 출력하는 함수이다.
    -> 모두 같은 의미.
  • Neighbor Aggregation Function이 Neighbor Structure에 따라 Injective하게 Embedding을 Mapping하면 강력한 표현능력을 가졌다고 할 수 있다.

🔨 Neighbor Aggregation

• 중복되는 원소가 있는 집합(Set)에 대한 함수로 정의된다.
• Injective한 Aggregation을 하려면 입력의 모든 특성(원소의 등장 횟수, 생상별 등장 비율 등)을 Embedding에 반영해야 한다.

✔️ GCN (Mean Pooling) -> Not injective

GCN은 위와 같이 같은 색의 비율을 가진 Multi-Set을 구부할 수 없기 때문에 Injective 하지 않다.

Element-Wise Mean은 색상별 원소의 비율이 동일하면 같은 결과를 도출한다. Linear은 가중치를 공유하기 때문에 Pooling의 결과가 같으면 Linear + Relu의 결과도 같기 때문에 일대일 대응이 되지 않는다.

✔️ GraphSAGE (Max Pooling) -> Not injective

Element-Wise Max는 사용한 색의 종류가 같으면 같은 결과가 도출된다. 빈도에 상관없이 같은 색상의 입력이라면 MLP의 결과값이 같고, MLP + Max Pooling의 결과 역시 같아진다. 일대일대응이 깨진다.

🔨 Injective Multi-set Function(GIN)

• Most Expressive GNN!

• GCN이나 GraphSAGE가 단사합수가 되지 못한 이유
  (1) 이웃 노드의 개수를 고려하지 못했다 (2) 노드의 종류를 고려하지 못했다

  
  

  • Multi-set 내의 모든 요소에 함수 f 적용
  • Multi-set 합산 -> injective
  • 합산한 결과에 non-linear 함수 적용

Reference

https://www.youtube.com/watch?v=RU9uTa_-ZOw&list=PLoROMvodv4rPLKxIpqhjhPgdQy7imNkDn&index=20