NGCF: Neural Graph Collaborative Filtering

 NGCF 이전의 방법들은 User-ID, Attribute와 같은 pre-existing features를 단순히 Mapping하여 추천 시스템의 embedding으로 사용했다.  Node간 관계를 고려하지 않은 채 features를 그대로 이용할 경우 user-item의 높은 차원에서 상호 관계(Collaborative-Signal)를 충분히 반영하지 못하게 된다. NGCF의 저자는 이러한 점을 지적하며  bipartite graph 구조를 활용하여 user-item interaction을 더 반영한 emebdding propagation 방법을 제안했다.

 

Bipartite Graph

 bipartite graph(이분 그래프)는 그래프에서 노드가 두 개의 집합(집단)으로 나눠진다고 했을 때 같은 집합 간의 노드에는 서로 이어진 엣지가 없고 서로 다른 집합 간의 노드에만 엣지가 존재하는 그래프 구조를 말한다. NGCF에서 말하는 bipartite graph는 user-item interaction graph이다.

왼쪽에 있는 노드 집합 u는 3명의 user들을 의미하고 오른 쪽의 노드 집합 i는 5개의 item을 의미한다. user 끼리, item 끼리는 서로 연결되어 있지 않은 것을 볼 수 있다.  bipartite graph의 구조를 이용하여 emebdding-propagation(message passing)을 진행하면 graph에 존재하는 high-order connectivity(노드로 부터 떨어진 거리에 따른 정보)를 embedding에 담을 수 있게 된다.

 

 위 그림은 bipartite graph에서 user u1에 대한 hige-order connectivity를 나타낸다. 왼 쪽의 bipartite graph를 살펴보면 u_{1}은 i_{1}, i_{2}, i_{3}과 연결되어 있고 i_{2}는 u_{2}, i_{3} 는 u_{3}과 연결되어 있다. 오른 쪽 그림은 bipartite graph의 u_{1}에 대한 정보를 High-Order Connectivity를 관측하기 쉽게 끔 펼쳐놓은 것이다.

특징을 살펴보면 첫번째 order에서는 user 1과 1-hop으로 연결된 Node, item들만 있는 것을 알 수 있고 두 번째 order에서는 user들만이 있는 것을 알 수 있다. 특히 두 번째 order에서는 user들 간 유사도를 발견할 수 있다. 유사도가 높은 user들 끼리는 구매할 상품이 비슷할 것이라 예측할 수 있다. u_{1} - i_{2} - u_{2} - i_{4} 로 이어지므로 u_{1}이 i_{4}를 구매할 확률이 높다. i_{4}와 i_{5} 모두 u_{1}과 비슷한 user들이 구매한 상품인데 i_{4}의 경우 order 3에서 2개가 존재 하므로 i_{5}보다 더 높은 추천 점수를 가져야 할 것이다.

 

 

Embedding Propagation Layers

 

NGCF에서 제안한 embedding-propagation은 layer에서 얻은 embedding들을 stacking하여 각 계층의 정보를 보존한다. layer 1에서는 user_{1} 이 관심있는 품목(i_{2}, i_{3})에 대한 embedding ,layer 2 (u_{2}, u_{3}) 에서는 비슷한 행동양상을 보인 user들과 similarity 정보를 담은 embedding, layer 3 (i_{4}, i_{5})에서는 잠재적 추천 상품들에 대한 embedding이 담긴다. layer 3에 대한 embedding에는 위에서 살펴봤던 i_{4}와 i_{5}와 같이 추천에 있어 우선 순위에 관한 정보가 포함되어야 한다.

 

 

 

  Embedding Propagation Layer의 그림이다. 전체적인 흐름을 살펴보면 먼저 user에 대한 feature와 user에게 추천할 item에 대한 feature가 각각 들어가서 3번의 embedding propagation 과정을 거친다. embedding propagation 과정은 higher order connectivuty의 순서에 맞게 진행됨을 알 수 있고 l=1, l=2, l=3 각각에서 나온 embedding을 concatenation해서 사용한다. concatenation해서 완성된 user와 item 각각에 대한 final embedding은 y_NGCF라는 것을 통해 score로 계산되는데 이는 단순한 내적을 의미한다.

 

l 마다 이뤄지는 Message Propagation 크게 두 개의 과정으로 나눌 수 있다.

1. Message Construction

  message construction은 한 개의 노드로 부터 전달되는 message가 어떻게 구성되는 지를 나타낸다. 

 

 bipartite graph의 item node(e_{i})에서 user node(e_{u})로 전달되는 message이다. e_{i}와  e_{i}와 e_{u}의 element-wise product가 가중치에 곱해져 더해져서 e_{u}와 e_{i}의 degreee의 root값으로 normalization되고 있다. 주어진 수식에서 item에서 user로 전달되는 message를 살펴보면 normalization을 통해 degree가 높은 노드의 영향력을 줄이고 item의 embedding을 기본으로 두고 해당 item과 user간 유사한 정도를 더해서 user의 embedding으로 전달한다는 의미를 가지고 있다.

  element-wise product는 hadamard product라고도 불린다. element-wise product는 두 벡터의 같은 차원에 있는 원소들을 곱한 후 곱한 값을 모두 더해 스칼라를 만드는 dot product와 달리 두 벡터의 같은 차원에 있는 원소들을 곱해 만들어지는 새로운 벡터를 말한다. 같은 차원의 값이 모두 같은 부호를 가지고 큰 값을 가지게 되는 경우 해당 차원의 값이 커지게 되고 두 차원 모두 0에 가까운 값을 가지게 되면 해당 차원의 원소는 작은 값을 가지게 된다. 같은 차원의 원소가 부호가 다른 경우에도 음수의 값을 가지게 되므로 두 벡터간 유사한 점과 다른 점에 대한 정보를 가지게 된다. 

 normalization에 담긴 의미는 연결된 노드의 수(Degree)가 많아지면 그만큼 받게 되는 정보가 많아지게 되는데 받는 정보, Message가 많아질 수록 한 개의 Message가 같는 중요도는 상대적으로 적어짐을 의미한다. 학습의 관점으로 봤을 때는 Normalization 없이 학습이 된다면 dgree가 높은 노드가 여러 노드로부터 Message를 받게 될 것이므로 노드의 feature가 매우 큰 값을 갖게 될 것인데  degree가 높은 노드의 상태에 따라서 다른 노드의 학습에 큰 영향을 미칠 수 있으므로 여러 노드의 Message를 공평하게 보기 위함이라고도 볼 수 있다.

 

 

  l번째 embedding propagation layer에서 생성되는 e_{u}의 embedding이다. m_{u<-u}, 이전 layer의 u에서 현재 layer의 u로 가는 message가 추가된 것을 알 수 있다. 이때 이전 layer에 곱해지는 가중치 W1은 이전 layer의 e_{i}에 곱해지는 가중치 W1과 공유된다. P_ui는 Normalization 을 간략하게 나타낸 것이다.  Leaky ReLU를 사용한 이유는 element-wise product로부터 강조된 유사성은 큰 양의 값을 가지게 될 확률이 높고 다른 점은 0에 가깝거나 음수의 값을 가질 확률이 높은데 양수의 값을 크게 남김으로써 message로 받은 정보 중 유사성을 남기기 위함이라고 생각할 수 있다.

 

 논문에서는 이 과정을 벡터가 아닌 행렬의 형태로 나타내었다.

 

 위 행렬들의 Notation을 파악해 보겠다. 먼저 A는 N개의 User 노드와 M개의 Item노드의 Adjacency Matrix를 의미한다. A는 user-item relation matrix를 의미하는 R과 정사각 0행렬들 그리고 R의 전치행렬로 이뤄져 있다. A의 행을 기준으로 첫번 째 부터 N 번째 행은 User에 관한 행, R의 전치행렬이 나타내는 N+1번째 부터 N+M번째 행까지는 Item에 관한 행이라 이해할 수 있다. L은 Normalization된 Adjacency Matrix이다. D는 Degree Matrix이다. D^{-1/2}로 A의 앞 뒤에 곱해져서 Normalization이 된다. Degree Matrix는 순서대로 노드의 degree가 대각원소로 나열된 대각 행렬이다. A의 앞 뒤에 곱해지고 있으니 행과 열의 크기가 N+M인 A를 따라 D도 행과 열의 크기가 N+M일 것이고 degree의 순서는 N개의 user 먼저 그 다음에 M개의 item에 대한 degree가 올 것이다. 

 

 위와 같은 행렬 표현은 앞으로 논문을 읽을 때나 실제 모델의 코드를 작성할 때 참고가 될 수 있으므로 조금 자세히 살펴보겠다.

 

 R은 N명의 user와 M개의 item의 관계를 나타내는 행렬이다. N행 M열을 가졌으므로 행은 user를 나타내는 것이고 열은 item을 나타낼 것이다. R(i,j)의 원소 a_{i,j}는 user i와 item j의 관계를 나타낸다. user_{i}가 item_{j}의 구매 경험이 있다면 a_{i,j}는 1의 값을 가질 것이고 없다면 0의 값을 가질 것이다. R을 행을 기준으로 보면 user에 대한 정보를 중심으로, 열을 기준으로 본다면 item에 대한 정보를 중심으로 볼 수 있다.

 

 

 adjacency matrix는 R과 R의 전치행렬 그리고 좌측 상단에는 NxN 0행렬 우측 하단에는 NxN의 0행렬이 존재한다. 각각의 행은 순서대로 user_1 부터 user_N, item_1부터 item_N 까지를 나타낸다고 볼 수 있다. 0행렬들이 포함되는 이유는 행렬 곱으로 나타낼 때 포함될 정보와 포함되지 않을 정보들을 고르기 위함이다. NGCF는 bipartite graph의 구조를 이용해서 higher order connectivty를 얻는 게 목적이므로  행렬 곱으로 인해 user와 user, item과 item의 정보가 직접적으로 이어져서는 안된다.

 

 Degree Matrix의 형태이다. D_u1은 user_1의 degree D_i1은 item_1의 degree를 나타낸다. L은 D^{-1/2}를 A의 앞 뒤로 곱해준다. 이를 symmetric normalization이라고 한다. symmetric normalization에 익숙하지 않은 사람들을 위해 어떻게 이뤄지는 지 예를 들어 설명해 보겠다. 

 

NxN 대각행렬 C와 NxN 행렬 B가 있다.

 

먼저 CB의 상황, 대각행렬 C를 B의 앞에서 곱해주는 상황을 살펴보면 

 C의 대각원소가 순서대로 B의 각각의 행에 곱해지는 것을 볼 수 있다. 행렬 곱의 결괏 값의 행을 하나하나 살펴보면 뒤에 오는 행렬의 행의 결합으로 볼 수 있다. 위와 같은 상황에서 C의 첫번 째 행을 살펴보면 첫번 째 열의 원소 c1을 제외한 모든 열의 원소가 0이므로 c1b1. + 0*b2. + ... +0*bn.=c1b1.이다. 나머지 행에 대해서도 마찬가지이다.

 

 C가 B의 뒤에서 곱해지는 경우 C의 대각원소가 B의 열에 곱해지는 것을 볼 수 있다. 행렬 곱의 결괏 값을 열을 기준으로 살펴 보면 각각의 열은 앞에 오는 행렬의 열의 결합으로 볼 수 있다. C의 첫번 째 열을 살펴보면 c1외에 다시 모든 원소가 0이다 따라서 BC의 첫번째 열은 c1*b.1 + 0*b.2 + .. + 0*b.n = c1*b.1이다.

 

앞 뒤에서 모두 곱해진다면 이러한 형태가 될 것이다. 행과 열의 개수의 조합(nC2) ci*cj의 조합이 나올 것이다.

 

이를 L에 대해 나타내 보면 

 

이런 식으로 계산된다. Degree Matrix의 원소들을 논문에 나온대로 교체했다.(헷갈리게 해서 죄송합니다.)

 

 

각 layer에서 Node에 대한 정보는 embedding matrix E에 저장되어 있다.

 

 다시 행을 기준으로 user와 item의 embedding을 둔다면 E의 형태는 아래와 같을 것이다.

 

 

 embedding propagation layer의 message passing 과정을 살펴보겠다.

 

L+I 는 Normalization Matrix에 Identity를 더한 것인데 이는 

 

Message에 포함되어 있는 자기 자신의 embedding을 E로부터 look up 하기 위함이다. 그래서 (L+I)EW을 살펴보면

 

 

L에 I가 더해짐으로써 E에서 스스로를 추출할 수 있게 되었고 E에서 추출된 행끼리 결합하여 학습되는 W1으로 인해 더 적절한 벡터 공간으로 Mapping이 되는 것이다.  

 

  W1에 곱해지는 행렬에 대한 식의 설명은 끝났고 W1에 곱해지는 행렬에 대한 설명을 해보겠다.

 

 

W2에 곱해지는 message에는 item, user W1과 곱해지는 message와 달리 스스로에 대한 정보가 필요하지 않는다 따라서 L에 I가 더해지지 않는 것이다. LE는 현재 처리되고 있는 노드와 연결되어 있는 그래프들의 embedding만 look up 하는 것이다. 따라서 LE는 현재 처리되고 있는 노드가 item이라면 이전 layer에서 user에 대한 embedding의 결합을 뜻하고 현재 처리되고 있는 노드가 user 라면 이전 layer에서 item에 대한 emebdding의 결합을 뜻한다. 

 

 

 

 각각의 행이 노드의 feature를 뜻하고 N개의 user의 feature는 이전 layer의 M개의 item중 연결된 노드 와의 emebdding으로만 구성되고 M개의 item에 대한 embedding은 이전 layer의 N개의 user 중 연결된 노드와의 embedding으로만 구성된다. 

 다음으로 LE에 대해  E와 element wise product를 생성하는데 이는 item으로 형성된 embedding과 현재 처리 중인 노드와의 유사한 특성을 추출하기 위함이다.

 

 

새롭게 형성된 user는 item으로부터 형성된 embedding, E_u와 item은 user로부터 생성된 embedding, E_i를 이전 layer의 자신에 대한 embedding과 element-wisr product를 진행해 유사한 차원을 강조하는 embedding을 가지게 된다.

위 과정을 합치면 이렇게 쓸 수 있고 E_u, E_i 등은 시그마를 뜻한다.

 

Loss Functin으로는 두 가지 서로 다른 embedding을 비교하여 학습해 나가는 BPR Loss를 사용했는데 BPR Loss에 대한 내용은 추후 다뤄 보겠다.

 

Model Size

 한 layer에서 학습되는 가중치는 W1과 W2 밖에 없다. layer마다 dimension의 크기가 d로 모두 같다고 하고 layer의 개수가 n개 라고 할 때 2*n * (d*d)정도로 매우 작은 학습 파라미터가 소요된다.