He 2020 - LightGCN

He 2020 - LightGCN is a simple and effective Graph Convolution Network for recommendation.

LightGCN is an adaptation of Graph Convolutional Neural Networks (GCN) to the task of recommendations. In a typical Convolutional Neural Network for vision, convolution aggregations (such as linear projections, pooling, average) are applied to a neighbourhood of pixels that are near to one another. The aggregations transform the raw pixel values into a hidden layer of "embedding" values, and the next layer of aggregations is applied to the hidden layer, allowing the CNN to learn more abstract features with each increasing layer. A GCN uses essentially the same idea, except that the definition of neighbourhood of a node A are the neighbouring nodes that are connected by an edge to A. The GCN thus allows us to train node embeddings on all types of graphical data, such as social networks, user-item interactions etc.

Setting

This paper tackles the task of collaborative filtering without features, i.e. making recommendations purely from the user and item id. Also, no negative samples are required - all we need is edges between users and items based on some form of implicit interaction.

Neural Graph Collaborative Filtering (NGCF)

The LightGCN model is essentially a simplification of the NGCF model, so the paper starts here. Btw, there are some overlaps between LightGCN authors and NGCF authors. The setup is as follows:

• Each user and item are embedded from their id -> embedding
• Let $e_u^{(0)}$ denote the ID embedding of user $u$ and $e_i^{(0)}$ denote the ID embedding of item $i$

NGCF uses the user-item interaction graph (derived from data) to propagate the embeddings as follows: $$\begin{array}{rl}{e}_u^{(k+1)}& =\sigma \left(W_1^{(k)}{e}_u^{(k)}+\sum _{i\in {\mathcal{N}}_u}\frac{1}{\sqrt{|{\mathcal{N}}_u||{\mathcal{N}}_i|}}\left(W_1^{(k)}{e}_i^{(k)}+W_2^{(k)}(e_i^{(k)}\odot e_u^{(k)})\right)\right)\\ e_i^{(k+1)}& =\sigma \left(W_1^{(k)}{e}_i^{(k)}+\sum _{u\in {\mathcal{N}}_i}\frac{1}{\sqrt{|{\mathcal{N}}_u||{\mathcal{N}}_i|}}\left(W_1^{(k)}{e}_u^{(k)}+W_2^{(k)}(e_i^{(k)}\odot e_u^{(k)})\right)\right)\end{array}$$

Some notes about the propagation equations above:

• $e_u^{(k+1)}$ and $e_i^{(k+1)}$ denote the embedding of user $u$ and item $i$ respectively after k layers of propagation
• $\sigma$ is a non-linear activation function
• ${\mathcal{N}}_u$ denotes the set of items that interacted with user $u$. For instance, it could be all the items the user purchased within the past 3 months. ${\mathcal{N}}_i$ is the set of users defined in a similar way.
• $W_1^{(k)}$ and $W_2^{(k)}$ are trainable weights

Intuitively for a given user, the equation propagates (i) the user embeddings itself (order-1), (ii) the embeddings of neighbouring items (order-1) and (iii) the hadamard interaction between the user and the neighbouring items (order-2). And likewise for the item embeddings. Note that is performed - the entire neighbour set is taken per node.

Finally, after training the network of $L$ layers, we obtain $L+1$ embeddings for each user and item. The embeddings are concatenated as such $e_u=[e_u^{(0)},...,e_u^{(L)}]$ and $e_i=[e_i^{(0)},...,e_i^{(L)}]$ where $e_u,e_i$ are vectors of dimension ${\mathbb{R}}^{kL}$. Prediction scores for the match between user $u$ and item $i$ are then computed via the inner product $⟨e_u,e_i⟩$.

Problem With NGCF

The authors argue that NGCF is unnecessarily complicated because traditionally, the base embedding layer $e_u^{(0)},e_i^{(0)}$ is derived from rich semantic features such as embedding the title of papers etc. This justifies the usage of the activation function $\sigma$ and the projection weights $W_1^{(k)},W_2^{(k)}$ etc. to learn a transformation of the semantic features. In contrast, for the collaborative filtering setting, the embeddings are arbitrary numbers tied to each user or item ID. Hence, performing multiple non-linear transformations will not lead to better feature learning.

: I'm not fully convinced by this argument, although the empirical results do support it. I agree with the argument to the extent that the base embedding layer is arbitrary, but imo NGCF can still learn a bigger representation space of models through its non-linear transformations. The problem seems to be more that (i) the richer feature representation is not very useful and (ii) the additional complexity makes the model harder to learn.

LightGCN Forward Propagation

In LightGCN, we essentially remove the non-linear activation and weight projections. The propagation equations simplify to the following:

$$\begin{array}{rl}{e}_u^{(k+1)}& =\sum _{i\in {\mathcal{N}}_u}\frac{e_i^{(k)}}{\sqrt{|{\mathcal{N}}_u||{\mathcal{N}}_i|}}\\ e_i^{(k+1)}& =\sum _{u\in {\mathcal{N}}_i}\frac{e_u^{(k)}}{\sqrt{|{\mathcal{N}}_u||{\mathcal{N}}_i|}}\end{array}$$

The final representation of each node $v$ (whether user or item) is then a weighted sum of its hidden representation across all layers:

$$e_v=\sum _{k=0}^K{\alpha }_k\cdot e_v^{(k)}$$

Although ${\alpha }_k$ could be a parameter to be optimized, the authors propose just setting ${\alpha }_k=1/(K+1)$ for simplicity.

Noticeably, the forward propagation does not include the self-connection from the previous layer, i.e. the update for $e_u^{k+1}$ does not explicitly include $e_u^k$, which other papers like GraphSAGE argue is important. The authors argue that because they use a weighted sum of hidden representations across all layers, this essentially is equivalent to including self-connections, so that is no longer necessary.

Loss

The only trainable parameters of the model are the embeddings at the 0th layer, i.e. $E^{(0)}$. The authors propose using loss, which is a pairwise loss that encourages the score of a neighbour to be higher than the score of an unobserved, randomly sampled counterpart.

$${\mathcal{L}}_{BPR}=-\sum _{u=1}^M\sum _{i\in {\mathcal{N}}_u}\sum _{j\notin {\mathcal{N}}_u}ln\sigma ({\hat{y}}_{ui}-{\hat{y}}_{uj})+\lambda ||E^{(0)}|{|}^2$$

In contrast to NGCF and other GCN approaches, the authors do not use dropout as a regularizer. Instead, they think the L2 regularization on the embedding layer is sufficient, as these are the only parameters in the model. Training of the model is done in a mini-batch manner, where batches of (user, item) tuples are drawn, negative items sampled, and the loss evaluated.

Ablation Studies

The paper has a few ablation findings:

1. is important, i.e. it is important in the forward propagation to divide by $\sqrt{|{\mathcal{N}}_u||{\mathcal{N}}_i|}$. Omitting either one leads to performance degradation. Note that in GraphSAGE, the GraphSAGE-mean variant essentially does ${\sum }_{i\in {\mathcal{N}}_u}{e}_i^{(k)}/|{\mathcal{N}}_u|$, i.e. it only normalizes by the user degree. I suppose normalizing by the item degree as well penalizes popular items, so it could be useful.
2. is important for robustness as we increase the number of layers, i.e. instead of just taking $e^K$ as the final embeddings, it is useful to take the element-wise mean of the embeddings at each layer. This might be analogous to the impact of including self connections.

References

• Medium Post by Hikaru Hotta and Ada Zhou
• LightGCN Paper
• NGCF Paper