Shallow Encoding (embedding lookup)
- 임베딩 행렬에서 노드의 임베딩 벡터를 각 column에 담아 단순히 벡터를 읽어오는 방식
- 노드 간에 파라미터를 공유하지 않기 때문에 노드 개수가 증가하면 행렬의 크기도 커진다
- 훈련 과정에서 보지 못한 노드는 임베딩을 생성할 수 없다.
- 노드의 feature 정보는 포함되지 않는다.
노드의 유사도는 랜덤워크나 딥워크와 같이 이전의 개념과 동일하지만 Encoder의 구조가 달라진다. 단순히 look-up만 하는 임베딩 방식의 한계를 극복하기 위해 다중 레이어로 구성된 encoder를 활용한다.
✔️ Differences
- complex topological structure
- No fixed node ordering or reference point
- Often dynamic & multimodal feature
- local 개념이 불분명하고 뒤집거나 회전시켜도 변하지 않는다.
- 멀어보이는 노드도 실제로는 짧은 경로로 연결되어있을 수 있다.
✔️ Notation
- V : 노드들의 집합
- A : 인접행렬(binary)
- X : node feature 행렬
- N(v) : v의 이웃노드 집합
GCN은 CNN의 아이디어를 그래프에 접목한 개념이다.
왼쪽 그래프에서 A 노드에 대해 2 hop node까지 계산그래프를 생성한 것이 오른쪽 그림이다. 오른쪽 가장 위를 보면 A와 C 노드에서 정보가 B로 흘러간다. A와 C 노드에 해당하는 임베딩 벡터를 입력으로 하여 정보가 합쳐져 레이어를 통과한다. 이렇게 B로 모아진 정보는 기존 B의 임베딩 벡터와 연산이 이루어진다. 타깃이 된 A 노드 역시 이웃노드 B,C,D로부터 정보를 받아 연산이 이루어진다.
-> 각 노드마다 이웃 노드로 부터 정의된 computation(계산) 그래프의 모습이다.
각 노드 별로 모델 구조가 다르다. E와 F 노드의 경우 동일한 계산 그래프를 가지고 있기 때문에 동일한 모델을 통해 처리될 수 있다.
✔️ Neighborhood aggregation
이웃 노드로부터 정보를 집계하는 방식은 네트워크 마다 상이하다. 집계하는 함수는 permutation invariant (입력 데이터 순서에 영향을 받지 않는) 함수여야 하며, 기본적인 방식은 정보를 average 하는 기법을 사용한다.
- 0번째 layer = node feature로 초기화
- (k+1)번째 layer = k번째 layer 임베딩에 weight matrix를 곱하고 이웃노드들의 hidden state의 평균을 weight matrix에 곱하여 더한다. 그 후 non-liearity를 부여.
- L번 layer을 거친 임베딩 결과 = Zv
- W : weight matrix for neighborhood aggregation
- B : weight matrix for transforming hidden vector of self
- W,B는 layer 마다 상이하며, 같은 layer에서는 모든 node들이 동일하다.
✔️ Goal : Node embedding Zv
✔️ input : Graph
✔️ Unsupervised setting ( 비지도 학습 )
- Node의 레이블이 없는 경우
- 그래프 구조를 supervision으로 사용
✔️ Supervised setting [Node classification]
- 실제 라벨과 node embedding 결과갑과의 loss function을 정의하여 학습시킬 수 있다.
GNN이 달성한 성과
계산 그래프의 구조와 관계없이 layer에 따라 Wl, Bl이 공유된다.
- 학습에 사용되지 않았던 노드들도 임베딩 벡터를 효과적으로 생성할 수 있다(Inductive Capability)
- 기존에 존재하는 그래프를 이용해 GNN을 학습시키고 새로운 노드를 추가할 때에도 추가 학습없이 임베딩 벡터를 생성할 수 있다.
- 기존에 look up만 사용한 방식에서 학습에 사용되지 않은 데이터를 임베딩하지 못하거나 노드 변수를 충분히 활용하지 못하는 문제점에서 탈피.
https://www.youtube.com/watch?v=F3PgltDzllc&list=PLoROMvodv4rPLKxIpqhjhPgdQy7imNkDn&index=17