GNN은 (1) Node의 Local Neighborhood로부터 (2) NeuralNet으로 정보를 Aggregation해 Embedding을 만드는 것
각 모델마다 다른 Propagation, Aggregation, Transfomation 방법론을 가지고 있다.
GCN(Mean-Pooling)
- Element-Wise Mean Pooling으로 Aggregation(이웃들의 정보 수집) 한뒤, Linear(선형변환) + Relu를 적용한다.
GraphSAGE(Max-Pooling)
- Element-Wise Max Pooling으로 Aggregation 한뒤, MLP로 모아진 정보를 가공.
- 1-hop Degree를 이용하면 3,5번 node는 구분이 가능하다.
- 2-hop Degree까지 늘리면 4번까지 구분이 가능하지만, 1번과 2번 노드는 대칭구조이기에 hop를 늘려도 구분할 수 없게된다.
- 입력값으로 주어지는 그래프의 각 노드가 임의의 인코더를 통과하여 임베딩 공간에 위치하는 벡터로 바뀌는 과정.
- 이 과정을 통해 그래프에서 유사한 노드들이 임베딩 공간에서도 근처에 있도록 맵핑한다.
✔️표현력이 좋은 GNN
- 다른 트리 구조를 가지는 노드에 대해 항상 다르게 임베딩하는 것을 의미한다
- subtree를 임베딩으로 일대일대응(Injective)시킨다
- 다른 계산그래프에 대해 각각 다른 임베딩 벡터를 출력하는 함수이다.
-> 모두 같은 의미.- Neighbor Aggregation Function이 Neighbor Structure에 따라 Injective하게 Embedding을 Mapping하면 강력한 표현능력을 가졌다고 할 수 있다.
✔️ 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의 결과 역시 같아진다. 일대일대응이 깨진다.
GCN이나 GraphSAGE가 단사합수가 되지 못한 이유
(1) 이웃 노드의 개수를 고려하지 못했다 (2) 노드의 종류를 고려하지 못했다
- Multi-set 내의 모든 요소에 함수 f 적용
- Multi-set 합산 -> injective
- 합산한 결과에 non-linear 함수 적용
https://www.youtube.com/watch?v=RU9uTa_-ZOw&list=PLoROMvodv4rPLKxIpqhjhPgdQy7imNkDn&index=20
우와 정말 유용해요!