Source-linked AI summary
Graph Convolutional Matrix Completion
Rianne van den Berg, Thomas N. Kipf, Max Welling
TL;DR
Matrix completion in recommender systems is treated as labeled-link prediction on bipartite user-item graphs. The paper proposes GC-MC, a graph auto-encoder using message passing and a bilinear decoder, and reports competitive benchmark performance, with large-margin gains when side information is available. The framework also supports larger-scale training through stochastic mini-batching.
Problem
Matrix completion must predict unobserved ratings or purchases from user-item interaction data, including settings with user or item side information.
Method
GC-MC learns user and item embeddings through graph convolutional message passing on a bipartite interaction graph and predicts labeled rating edges with a bilinear decoder.
Results
The model achieves competitive collaborative-filtering results and outperforms recent related methods by a large margin when feature- or graph-based side information is available.
Takeaways & Limitations
The graph auto-encoder naturally incorporates side information and can be trained on larger-scale datasets through stochastic mini-batching.
Takeaways & Limitations
The demonstrated encoder is one relatively simple choice; alternative message transformations, normalization schemes, and attention mechanisms remain open possibilities.
Abstract
from arXiv · showhide
We consider matrix completion for recommender systems from the point of view of link prediction on graphs. Interaction data such as movie ratings can be represented by a bipartite user-item graph with labeled edges denoting observed ratings. Building on recent progress in deep learning on graph-structured data, we propose a graph auto-encoder framework based on differentiable message passing on the bipartite interaction graph. Our model shows competitive performance on standard collaborative filtering benchmarks. In settings where complimentary feature information or structured data such as a social network is available, our framework outperforms recent state-of-the-art methods.
1 Introduction
The paper reframes recommender-system matrix completion as labeled-link prediction on bipartite user-item graphs and proposes a graph auto-encoder to solve it. The framework also incorporates node features and structured external information such as social networks.
- Matrix completion is formulated as link prediction on a bipartite graph, with users and items as nodes and observed ratings or purchases as links.
- Content information can be represented as node features, while rating prediction becomes prediction of labeled links in the user-item graph.
- GC-MC uses a graph-based auto-encoder that learns latent user and item features through message passing on the interaction graph.The learned representations reconstruct rating links through a bilinear decoder.
- Combining interaction data with structured external information can alleviate cold-start performance bottlenecks.The framework combines such side information without recurrent frameworks.
- The paper reports competitive performance on collaborative-filtering benchmarks and stronger results when feature or structured side information is available.
2 Matrix completion as link prediction in bipartite graphs
Matrix completion is reformulated as labeled link prediction on a bipartite user-item graph. GC-MC uses graph message passing to learn user and item embeddings, then reconstructs ratings with a bilinear decoder.
- Matrix completion as link prediction: Observed ratings define labeled edges in a bipartite user-item graph, while matrix completion predicts unobserved entries.The rating matrix encodes observed discrete ratings and missing values; the graph representation preserves rating levels as edge labels.
- Graph auto-encoders: Graph auto-encoders provide an end-to-end alternative to earlier multistage pipelines for graph feature extraction and link prediction.The framework builds on graph auto-encoders for unsupervised learning and link prediction.
- Graph convolutional encoder: GC-MC encodes user and item nodes through message passing over rating-specific adjacency matrices, producing separate user and item embeddings.The encoder passes transformed messages in both directions across the bipartite graph and can incorporate node features.
- Graph convolutional encoder: The encoder uses local first-order operations with shared transformations across graph locations and separate processing channels for rating types.Messages are normalized, transformed with edge-type-specific parameter matrices, and accumulated over neighbors.
- Graph convolutional encoder: Initial experiments found that a convolutional layer followed by a dense layer worked best, whereas stacking multiple convolutional layers did not improve performance.The model can support deeper combinations, but the reported initial configuration favored the simpler sequence.
- Bilinear decoder: A bilinear decoder treats each rating level as a separate class and predicts a probability distribution for reconstructed user-item ratings.The decoder operates on pairs of learned user and item embeddings using trainable rating-specific matrices and softmax.
3 Related work
Related work spans auto-encoders, matrix factorization, and matrix completion methods that incorporate user/item content or graph structure.
- Auto-encoders: User- or item-based auto-encoders are special cases of the graph auto-encoder model because their encoders consider only one embedding type.AutoRec projects a partially observed rating vector into a latent space and reconstructs it with mean squared reconstruction error.
- Auto-encoders: CF-NADE passes messages in only one direction and assigns unrated items a default rating of 3, creating a fully connected interaction graph.It also imposes a random node ordering and splits incoming messages via a random cut.
- Factorization models: Matrix factorization models approximate the rating matrix with a low-rank product whose user and item rows represent latent interest features.Probabilistic matrix factorization assumes Gaussian noise and minimizes mean squared error on observed entries.
- Matrix completion with side information: Classical matrix completion replaces intractable rank minimization with tractable nuclear-norm minimization.Inductive matrix completion incorporates user and item content through feature vectors in the rating approximation.
- Matrix completion with side information: Graph-regularized matrix completion adds user and item graphs as side information, with later work using alternating least squares or graph-based convolutional neural networks.These methods extend matrix completion beyond ratings by incorporating structured information about users and items.
4 Experiments
Experiments evaluate GC-MC across standard collaborative-filtering benchmarks, with and without side information, including larger datasets and cold-start users. The results show strong performance across graph- and feature-based settings, with side information especially valuable for users having very few ratings.
- Benchmark setup: GC-MC is evaluated on MovieLens, Flixster, Douban, and YahooMusic collaborative-filtering benchmarks using validation-selected configurations and reported test RMSE.The experiments include canonical splits, repeated runs, and datasets with user/item features or graphs.
- MovieLens 100K: MovieLens 100K comparisons evaluate GC-MC with and without user and movie side information against matrix-completion baselines.User features include age, gender, and occupation; movie features include genres.
- Graph side information: The Flixster, Douban, and YahooMusic datasets provide user and/or item graph side information integrated as normalized adjacency-based feature vectors.The side-information layer uses a dense embedding with ReLU activation, dropout, and concatenated message accumulation.
- Cold-start analysis: Side information is especially beneficial when many ML-100K users have only a single rating, based on cold-start experiments varying Nc and Nr.Figure 3 reports test RMSE averaged over five randomized runs, with and without side information.
- Comparative performance: On ML-100K, GC-MC outperforms related methods with side information and remains more effective without it, while larger-dataset results approach state-of-the-art collaborative filtering performance.The authors also report scalability to ML-1M and ML-10M.
- Benchmark results: GC-MC achieves state-of-the-art results on Flixster, Douban, and YahooMusic while using a single hyperparameter setting across all three datasets.These datasets contain user and item interaction graphs when available.
5 Conclusions
The paper introduces GC-MC, a graph auto-encoder that predicts ratings through message-passed user and item embeddings on a bipartite interaction graph. It incorporates side information, scales through stochastic mini-batching, and achieves strong benchmark performance.
- Conclusions: GC-MC uses graph convolutional message passing to construct user and item embeddings, then predicts ratings as labeled edges with a bilinear decoder.The framework is designed for matrix completion in recommender systems.
- Conclusions: The framework naturally incorporates side information for users and items and outperforms related methods on benchmark datasets with feature- and graph-based information.The conclusion describes the improvement as a large margin.
- Conclusions: Stochastic mini-batching enables training on larger-scale datasets, where GC-MC achieves performance competitive with recent state-of-the-art collaborative-filtering methods.Future work targets multimodal data and more efficient approximate schemes for scalability.