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 denote the ID embedding of user and denote the ID embedding of item
NGCF uses the user-item interaction graph (derived from data) to propagate the embeddings as follows:
Some notes about the propagation equations above:
- and denote the embedding of user and item respectively after
k
layers of propagation - is a non-linear activation function
- denotes the set of items that interacted with user . For instance, it could be all the items the user purchased within the past 3 months. is the set of users defined in a similar way.
- and 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
Finally, after training the network of layers, we obtain embeddings for each user and item. The embeddings are concatenated as such and where are vectors of dimension . Prediction scores for the match between user and item are then computed via the inner product .
Problem With NGCF
The authors argue that NGCF is unnecessarily complicated because traditionally, the base embedding layer is derived from rich semantic features such as embedding the title of papers etc. This justifies the usage of the activation function and the projection weights 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.
LightGCN Forward Propagation
In LightGCN, we essentially remove the non-linear activation and weight projections. The propagation equations simplify to the following:
The final representation of each node (whether user or item) is then a weighted sum of its hidden representation across all layers:
Although could be a parameter to be optimized, the authors propose just setting for simplicity.
Noticeably, the forward propagation does not include the self-connection from the previous layer, i.e. the update for does not explicitly include , 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. . The authors propose using
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:
is important, i.e. it is important in the forward propagation to divide by . Omitting either one leads to performance degradation. Note that in GraphSAGE, the GraphSAGE-mean
variant essentially does , 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.is important for robustness as we increase the number of layers, i.e. instead of just taking 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.