GCN
- eigen decomposition을 사용해서 noise 없는 feature를 뽑도록 하자
- 한 노드의 정보는 여러 노드로 부터오는 signal이 섞여 있어서, 이를 여러 signal로 나눠서 node의 특징을 잘 추출할 수 있다
- Spectrum representation을 얻기 위해서 퓨리에 변환과 Graph Laplacian을 정의함
- Graph Laplasian : L = D - A
<aside>
💡 ?? Laplasian
Laplasian Operator : differential operator로 벡터 기울기의 divergence를 의미하고, 한 노드의 흩어짐 정도를 알 수 있음.
→ 특정 노드의 signal과 특정 노드의 이웃노드의 signal의 변화량을 통해서 특정 노드의 signal 특징을 구한 것.
</aside>
- $H^{(l+1)} = \sigma(\tilde{D}^{-\frac{1}{2}}\tilde{A}\tilde{D}^{-\frac{1}{2}}H^{(l)}W^{(l)})$
- 위와 같이 Multi-layer로 제안을 함.
- 원래는 eigen value를 계산을 해야하지만, 쉬운 연산이 아니기 때문에
Chebyshev 방적식으로 spectral convolution을 근사를 하게 됨.
- 인접 행렬의 정보를 이용함으로, 1-hop으로 연결된 정보를 전부 이웃으로 정의하고 정보를 가져옴.
- 근사를 통해서, 계산을 하지만, 모든 노드 정보를 다 사용하기 때문에 tranductive (새로운 노드가 들어오면 전체를 다시 학습)
- inductive하게 한 FastGCN이 있음.
GraphSage
- 주변의 연결된 모든 정보가 아닌 Sampling과 aggregate를 통해서 node의 representation을 학습함.
- spatial model & inductive한 방법론
- 이 논문 전에 DeepWalk 가 있었음.
- 연결된 그래프에서 window size내에서 랜덤하게 이웃노드로 움직임.
- 그러면, 많이 연결이 되거나, 특정 노드로 갈때 많이 지나갈 꺼고, 확률적으로 임베딩이 유사하도록함.
- GraphSage에서도 유사하게 RandomWalk를 통한 Sampling을 수행함.
- Aggregate에 대하여는 Mean, Max, sum 등 사용G
- 샘플링 과정 설명
- full batch case
- k hop 거리 만큼 message passing을 함.
- 모든 노드들에 대해 1-hop propagation을 수행,
- 수차적으로 n hop에 대하여 정보를 업데이트 하게 됨.
- mini batch case
- 배치 단위에서 학습 될 노드 지정과 이웃 샘플링
- 랜덤 샘플링을 통해서 주변 노드에 대하여 선정하고, sub-graph를 만들게 됨.
- 샘플링으로 여러 sub-graph를 만들어 학습을 하게 됨.
- Aggregate 설명
- 노드에 대하여 순서에 무관해야함.
- 논문에서는 3가지를 제안 : mean, pooling, LSTM(순서를 랜덤으로 permution하여 입력함.)
GAT