//////
Search
Duplicate

임진수

과제여부

GCN

eigen decomposition을 사용해서 noise 없는 feature를 뽑도록 하자
한 노드의 정보는 여러 노드로 부터오는 signal이 섞여 있어서, 이를 여러 signal로 나눠서 node의 특징을 잘 추출할 수 있다
Spectrum representation을 얻기 위해서 퓨리에 변환과 Graph Laplacian을 정의함
Graph Laplasian : L = D - A
?? Laplasian Laplasian Operator : differential operator로 벡터 기울기의 divergence를 의미하고, 한 노드의 흩어짐 정도를 알 수 있음. → 특정 노드의 signal과 특정 노드의 이웃노드의 signal의 변화량을 통해서 특정 노드의 signal 특징을 구한 것.
H(l+1)=σ(D~12A~D~12H(l)W(l))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

Graph에서 주변 node의 정보를 가져올때, 가중치로 Attention을 사용
노드 주변 노드들 사이의 attention coeffiecient를 만들고 softmax를 통해서 정규화된 attention score를 만듬.
Attention Mechanism은 single-layer feedforward 를 사용
Aggregate
모드 노드들 사이의 n x n의 attention을 구함.
자기와 주변 노드들에 대하여 score를 결합해서 벡터를 계산