[论文笔记]Graph Convolutional Matrix Completion

[keywords]: recommender systems, link prediction, bipartite, graph auto-encoder framework, collaborative filtering

[1. Introduction]

Two main branches of recommender algorithms:

content-based recommender systems: use content information of users and items to predict the next purchase of a user or rating of an item.
collaborative filtering models: solve the matrix completion by collective interaction data.

matrix completion	link prediction on graph
interaction data	bipartite graph (between user and item nodes)
observed ratings/purchases	links
content information	node features
predict ratings	predict labeled links

[2. Matrix completion as link prediction on bipartite graphs]

$M_{N_u\times N_v}$ Rating matrix
$N_u$ : number of users, $N_v$ : number of items
$M_{ij}$ either an observed rating or 0 (unobserved)
$M_{N_u\times N_v}\iff G=(\mathcal{W},\mathcal{E}, \mathcal{R})$ : undirected bipartite user-item interaction graph
( $\mathcal{W}=\mathcal{U}\cup\mathcal{V}$ )

[2.1 Graph auto-encoders]

A graph encoder model $Z=f(X,A)$
A pairwise decoder model $\check{A}=g(Z)$

$X_{N\times D}$ : feature matrix
$A_{N:\times N}:$ adjacency matrix of a graph
$Z_{N\times E}$ : node embedding matrix ( $E$ : embedding size)
$M_r[i][j]=1\iff M[i][j]=r$
$U_{N_u\times E}$ : users embedding matrix
$V_{N_v\times E}$ : items embedding matrix
$\check{M}$ : a reconstructed rating matrix

$M_{N_u\times N_v}\iff G[X,A]\xrightarrow{\text{ f }}Z\xrightarrow{\text{ g }}\check{A}$
$M_{N_u\times N_v}\iff G[X, M_1,\cdots,M_R]\xrightarrow{\text{ f }}[U,V]\xrightarrow{\text{ g }}\check{M}$
Training: train the graph auto-encoder by minimizing the reconstruction error between the predicted ratings in $\check{M}$ and the observed ground-truth ratings in $M$ . (e.g. root mean square error, cross entropy)

[2.2 Graph convolutional encoder]

Idea: graph convolutional layer performs local operations that only take the first-order neighborhood of a node into account (can be seen as a form of message passing).
$\mu_{j\to i,r}=\frac{1}{c_{ij}}W_r x_j$
$h_i=\sigma[\text{accum}(\sum_{j\in \mathcal{N}_{i,1}}\mu_{j\to i,1},\cdots,\sum_{j\in \mathcal{N}_{i,R}}\mu_{j\to i,R})]$ (a graph convolutional layer)
$u_i=\sigma(Wh_i)$ (a dense layer)

$\mu_{j\to i,r}$ : edge-type sepcific messages from items $j$ to user $i$
$c_{ij}$ : either be $|\mathcal{N}_i|$ (left normalization) or $\sqrt{|\mathcal{N}_i ||\mathcal{N}_j|}$ (symmetric normalization)
$W_r$ : edge-type specific parameter matrix
$x_j$ : initial feature vector of node $j$
accum( $\cdot$ ): an accumulation operation (e.g. stack( $\cdot$ ), sum( $\cdot$ ))
$\sigma(\cdot)$ : an element-wise activation function (e.g. ReLU)
$u_i$ : final embedding of user node $i$