[Recommender System] - Graph Convolutional Matrix Completion 번역 & 리뷰

 

1. Intro

 

이 논문은 recommender system에서의 matrix completion 문제를 "link prediction on graph" 관점으로 바라본 내용을 서술하고 있다. 핵심 아이디어를 하나 예로 들면, user-item rating matrix를 user-item의 이분그래프로 표현할 수 있다는 것이다. 그리고 이를 graph auto-encoder 프레임워크에 응용하는 것을 제안한다. 논문에서 표현한 전체적인 그림은 아래와 같다.

 

---

2. Matrix completion as link prediction in bipartite graphs

 

그래프로 기존의 Rating Matrix를 표현하는 방식은 다음과 같다.

W는 User와 Item의 집합을 나타내는 기호이고, E는 Edge 정보, 그리고 R은 Rating에 대한 정보를 의미한다. 각각은 Graph에서 Node, Edge, Link의 역할을 하게 된다. 전체적인 구성은 이렇게 생겨먹었다.

 

---

1) Graph auto-encoders

 

이제 본격적인 내용으로 들어간다. 이번 논문의 메인 주제가 되는 Graph AE는 다음과 같이 구성되어있다.

이미지 출처 : https://leehyejin91.github.io/post-gcmc/

인코더는 Z로 표기되었으며, graph encoder model Z=f(X, A)의 수식으로 표현할 수 있다. 여기에서 X는 Node Feature Matrix를 의미하며, NxD의 dimension을 가지고 있다. 즉 user, item 각각에 대한 Dense Vector를 의미한다. Word2Vec과 같은 Embedding 방식으로 특성을 포함하는 벡터를 활용할 수 있다는 것이다. 단, 논문에서는 dimension이 동일한 user vector, item vector를 concat 한 것 처럼 표현되어 있는데, dimension이 반드시 같을 필요는 없다고 한다. 뭐 아마도 코딩하기 나름일 것 같다.

그리고 A는 Adjacency Matrix로, 각 node의 연결을 나타내는 인접 행렬이다. CF에서의 Rating Matrix를 떠올리면 된다. 다만 Edge가 존재하느냐의 여부만 가지고 있기 때문에, 모든 element가 binary이다. 만약 Rating Matrix의 Rating Value를 활용하고 싶은 경우, M5와 같은 Rating Adjacency Matrix로 표기할 수도 있다. (5점으로 연결된 Adjacency 만을 Matrix로 표현. 논문에서는 M1 ~ Mr의 Matrix를 활용하였음)

정리하자면 Encoder 모델은 X, A 두개의 행렬을 활용하여 Latent Factor를 만들어내는 작업이라고 할 수 있다. 이렇게 Graph AE의 구조를 간단하게 알아보았으니, 인코더에 대해 조금 더 자세히 알아보도록 하자.

 

---

2) Graph convolutional encoder

 

앞서 언급한 것 처럼, 본 논문에서는 1~5 사이의 Rating을 모두 다른 채널로 나누어 학습에 사용한다. 즉, Rating 마다 별도의 채널을 사용하는 그래프 네트워크를 만든다는 것이다. 이는 파라미터의 관점에서 5개의 다른 shared parameter가 존재한다는 것을 의미하기도 한다.

어찌되었든 Graph convolutional layer에서 핵심이 되는 아이디어는 weight sharing을 하는 (CNN의 필터 역할을 하는) 파라미터가 존재한다는 것이다. 그리고 이 관점에서 GC는 "first-order neighborhood of a node" 만을 message passing 방식으로 들여다보는 학습을 수행한다. 즉, CNN에서 중심점의 근방 n개 (ex : 3x3 filter)만을 convolutional 하듯이, 네트워크에서도 node의 1-depth 만큼의 연결만을 들여다본다. 그리고 그 각각의 iteration을 shared parameter로 학습하는 것이다. 이것을 Local Graph Convolution 이라고 하며 shared 파라미터를 Edge-type Specific Parameter라고 한다. (W_R로 표기하며, 후에 나오는 hidden layer <-> encoder 간의 파라미터 W와는 별개이다)

이해하기 쉽게 풀어쓰자면 1점을 부여한 user-item의 모든 관계를 W1로 학습하여 generalization 하고, 2점을 부여한 user-item의 모든 관계를 W2로 학습하여 generalization 한다는 것이다. 그리고 이를 이용하여 X와 W_R 두 행렬로 연산된 결과를 활용하겠다는 것이다. 마치 Matrix Factorization에서 user-item rating 값을 latent factor로 generalization 하는 것과 유사하다는 것을 알 수 있다. 다만 GC에서는 MF처럼 내적의 연산결과를 추정하는 것이 아니라, 관계 자체를 generalization 한다는 것에서 조금 더 나은 아이디어라고 볼 수 있다. 그리고 User와 Item의 Densed Feature를 활용할 수 있다는 점에서 꽤나 큰 성능 차이를 보일 것이다.

그렇다면 message passing이 무엇인지, shared parameter가 무엇인지를 아래의 수식으로 살펴보도록 하자.

 

Message passing은 결국 채널마다 고유하게 존재하는 벡터(message)가 user-item 네트워크를 돌아다니면서 학습에 영향을 미치는 개념이라고 생각할 수 있다. Graph의 모든 Edge를 타고 전달 및 변형이 이루어지기 때문에 Convolutional 한 학습이 이루어진다. Message passing 단계를 거치면 아래의 그림과 같이 h_i가 생겨나게 되는데, 이 결과가 바로 NN의 히든 레이어 역할을 하게 된다.

히든 레이어를 아래와 같이 한 번 더 통과시켜주면, output이 바로 임베딩 벡터가 된다.

지금까지의 내용을 간단히 정리해보면 아래와 같다. (나만 보려고 필기한 것이니 이해 안되면 패스해도 좋다)

 

---

3) Bilinear decoder

디코더 부분의 내용은 간단하다. MF에서는 간단히 user vector와 item vector간의 내적으로 이를 표현했지만, GCMC에서는 아래의 softmax의 개념을 사용하여 각 점수(r=1,2,...R)를 확률표현으로 나타낼 뿐이다. 

연산 결과 rating에 따른 확률의 분포가 생성되고, 이 수식에는 trainable parameter인 Q가 사용된다(ExE dimension). 그리고 최종적인 rating prediction은 아래의 수식을 한 번 더 거쳐 완성된다.

---

4) Model training

모델의 학습에 대한 언급은 총 3가지 인데 Loss function, Node dropout, Mini-batching에 관한 것이다. 이 중 뒤의 2개는 생략하도록 하겠다. 

Loss function은 아래와 같다. 일반적인 softmax 함수의 loss function과 구조는 동일하지만, MF에서 학습하는 것 처럼 interaction이 존재하지 않는 user-item rating의 경우는 mask 처리를 의미하는 기호들을 붙여놓았다. 즉, real interaction이 존재하는 i,j 에 대해서만 negative log likehood를 적용한다는 것이다.

---

5) Input feature representation and side information 

당연하게도 추천시스템을 구축하다보면, user 혹은 Item 단위의 피처를 모두 n-dimension vector로 잘 표현하기 힘들다. 그래서 잘 표현되지 않는 피쳐 정보를 input vector에 우겨 넣다보면 학습의 bottleneck을 초래한다. 그래서 이런 상황에서 해야 될 행동을 이 논문에서는 알려준다. 별로 까리하지 않은 피쳐가 있으면 input feature에 구겨넣지 말고, 차라리 hidden layer에 구겨넣으라는 것이다. 그리고 이는 아래와 같은 수식으로 간단히 표현되며, Side information이라고 한다.

수식에서 x_i_f는 히든 레이어에 직접적으로 전달되는 노드의 피처이고, W를 제외한 학습 파라미터들은 side information을 위해 새롭게 추가된 파라미터들이다. 논문에서 더 이상 자세한 설명을 담아두지는 않았지만, 피처가 부정확하게 표현되었을 경우 input feature로 활용하는 것 보다는 이런식으로 side information으로 활용하는 것도 좋은 방법이라고 한다. 연구진들이 좋은 결과를 목격했기 때문에 이 챕터를 넣어놨을 테지만, 논문 전체의 내용에서 그다지 중요한 챕터는 아닌 것 같다.

---

 

이하 내용은 벤치마크의 내용이며, 본 포스팅에서 언급하지 않았던 Weight Sharing 챕터만 추가해서 읽어보면 좋을 것 같다.

 

원문 링크 : arxiv.org/pdf/1706.02263.pdf

참고 자료 

- paperswithcode.com/paper/graph-convolutional-matrix-completion

Papers with Code - Graph Convolutional Matrix Completion

- leehyejin91.github.io/post-gcmc/

[논문 리뷰] Graph Convolutional Matrix Completion