[논문] Graph Convolution Matrix Completion(GNN)

추천시스템 #4 

이름만 들어본 GNN이 무엇인지부터 보자

1. GNN

GNN(graph neural network)는 아래와 같이 node, edge등으로 표현되는 graph 형태의 데이터를 모델링 하기 위한 네트워크이다. 

기존에 머신러닝에서 다루는 정형, 비정형(이미지, 텍스트, 오디오) 데이터들은 모두 n차원 유클리드 공간에 벡터와 행렬로 표현된다. 하지만 위와 같은 그래프 데이터는 유클리드 공간에 존재하지 않고, 직접적인 방법으로 벡터화 할 수 도 없다. 따라서 이를 기존 머신러닝 알고리즘에 넣기 위해 추가적인 network를 만들어, 유클리드 공간의 벡터와 행렬로 표현하고 이 네트워크(연산)를 aggregation function이라고 부른다. 

여러 종류의 GNN이 있으며, 이는 그래프 데이터를 행렬로 변환하는 연산(aggregation function)의 정의에 의해 결정된다.  여기선 aggregation function으로 convolution을 사용하는 GCN(graph convolution network)만 살펴보자.

 

2. GCN(graph convolution network)

A(N x N) : 인접 행렬, N개의 노드 사이가 연결되어 있으면 1 아니면 0, 정방 대칭 행렬이다

X(N x d): node feature matrix, N개 노드의 d차원 feature 벡터를 모아 둔 행렬

W(d x m) : weight, d차원 node feature를 m차원 latent feature로 보내는 함수(행렬) 

GCN에서 aggregation function 역할을 하는 graph convolution layer의 연산과정은 다음과 같다.

  1. X랑 W를 곱해서 n개의 노드에 대한 m차원 latent feature(S)를 만든

  2. A랑 S를 곱해서 각 노드의 인접 노드 latent feature vector로 구성된 N x m 차원 latent feature matrix(H)를 만든다

  3. activation function 통과 시킨다. 

이때, 인접 행렬 A를 그대로 사용하면, 특정 노드의 인접 노드 latent vector만으로 해당 노드의 최종 latent vector를 만들기 때문에, 자기 노드 feature vector가 반영 안되고, 정규화되어 있지 않아 S와 행렬곱 연산에서 bias가 발생한다. 따라서 모든 노드에 self-loop를 걸고(A + I), 다음과 같이 정규화 한다.

$D^{-\frac{1}{2}}AD^{-\frac{1}{2}}$

즉, GNN은 인접한 노드들의 정보와 

 

3. paper Graph Convolution Matrix Completion

왜 추천시스템에 그래프를 활용?

특정 user의 정보를 그 user와 관계를 맺고 있는 item들이 전달하는 메시지(rating, 정보)로 보다 구체적으로 표현하기 위해, 반대로 특정 item의 정보를 그 item과 관계를 맺고 있는 user들이 전달하는 메시지(rating, 정보)로 보다 구체적으로 표현하기 위함

이때, rating 별로 W를 공유하며, W_r 공간에 특정 user, item 정보를 표현하게된다. 이는 W를 하나만 쓰는 것보다 rating으로 나눔으로써 좀 더 구체적으로 정보를 표현할 수 있게 해준다.

user와 item vector를 각각 노드로 보고 연결 강도를 rating으로 사용, 기존 MF, CF와 다르게 외부에 구조화된 고유 feature 사용 가능(cold start 완화)

 GCN은 rating 별로 웨이트 공유, dense 웨이트는 전체가 동일하게 공유, GCN에서 각 W_r 공간으로 mapping된 latent vector들을 dense에서 W라는 공통된 공간으로 mapping해 디코딩 단에서 동일한 공간에서 해석이 가능하게 해준다.

결국 인코더로 임배딩 된 item, user latent vector로 predicted rating matrix를 디코딩하는 것!

원래 rating matrix M과 위에서 생성된 predicted rating matrix의 차이를 줄이는 방향으로 학습

*GCN layer가 쌓일수록 이웃 노드뿐만 아니라 연결된 다른 노드의 정보도 볼 수 있게 된다. 하지만 Bipartite graph이므로 parameter가 증가하는만큼 얻는 정보량이 많지 않아 논문에서는 GCN layer를 하나 쌓는게 가장 결과가 좋았다고 한다.

---

Q

인접행렬 A 정규화 하는 행렬 전개, 왜 이게 정규화가 되는건지 어떤 decomposition인지, 대각화?

행렬을 normalize 한다는게 정확히 어떤 의미? 유클리드 놈을 1로 맞춰주겠다는건가? 어떤 방향으로?

 

아래 식이 왜 x_j를 W공간에 표현한거가 되는지.. projection은 아닌거 같고 그냥 선형 결합인데 

A. 선형결합도 projection과 마찬가지로 W matrix 공간에 x vector를 표현하게 된다.

학습 초기에 feature matrix X는 랜덤하게 주는건가? 얘도 학습되는건가?