Source-linked AI summary
Geometric Matrix Completion with Recurrent Multi-Graph Neural Networks
Federico Monti, Michael M. Bronstein, Xavier Bresson
TL;DR
Matrix completion must recover missing ratings from sparse observations, while existing graph-based approaches do not fully exploit local stationarity and may scale their parameters with matrix dimensions. The paper uses geometric deep learning, combining multi-graph CNNs with an LSTM to model graph patterns and rating diffusion. Across synthetic and real datasets, the approach outperforms state-of-the-art recommender methods while using a constant number of parameters independent of matrix size.
Problem
Matrix completion recovers missing matrix values from sparse observations, but existing approaches do not fully exploit local graph stationarity and some formulations are difficult to scale to large matrices.
Method
The proposed architecture combines a multi-graph convolutional neural network with an LSTM recurrent neural network for graph-pattern extraction and nonlinear rating-diffusion modeling.
Results
The approach outperforms state-of-the-art recommender-system methods on synthetic and real-world datasets.
Takeaways & Limitations
The architecture uses a constant number of parameters independent of matrix size and demonstrates the potential of geometric deep learning for matrix completion on non-Euclidean domains.
Takeaways & Limitations
Spectral graph convolutions can require expensive O(n^2) operations on general graphs and lack guaranteed spatial localization.
Abstract
from arXiv · showhide
Matrix completion models are among the most common formulations of recommender systems. Recent works have showed a boost of performance of these techniques when introducing the pairwise relationships between users/items in the form of graphs, and imposing smoothness priors on these graphs. However, such techniques do not fully exploit the local stationarity structures of user/item graphs, and the number of parameters to learn is linear w.r.t. the number of users and items. We propose a novel approach to overcome these limitations by using geometric deep learning on graphs. Our matrix completion architecture combines graph convolutional neural networks and recurrent neural networks to learn meaningful statistical graph-structured patterns and the non-linear diffusion process that generates the known ratings. This neural network system requires a constant number of parameters independent of the matrix size. We apply our method on both synthetic and real datasets, showing that it outperforms state-of-the-art techniques.
1. Introduction
Matrix completion frames recommendation as recovering missing user–item ratings, while graph structure and geometric deep learning address the irregular organization of users, items, and ratings. The paper introduces a multi-graph CNN with an LSTM to extract graph patterns and model rating diffusion.
- Matrix completion: Matrix completion recovers missing user–item scores from a small subset of known matrix entries.The Netflix example contains 8.5B entries, with only 0.011% known.
- Graph structure: Graph-based matrix completion adds user and item similarity graphs, enabling smoothness notions that improve recommender-system performance.
- Geometric deep learning: Standard CNNs cannot directly process recommendation data because users, items, and ratings occupy irregular graph or manifold domains rather than regular grids.
- Geometric deep learning: Graph CNN research developed spectral and polynomial filtering approaches, including recurrent Chebyshev filters that reduce graph-convolution complexity.
- Main contribution: The proposed architecture combines a multi-graph CNN for local stationary patterns with an LSTM RNN for nonlinear rating-diffusion dynamics.
- Evaluation: The paper evaluates its techniques on synthetic and real-world datasets and presents the paper's organization around models, approach, experiments, and conclusions.
2. Background
Matrix completion recovers missing matrix entries under structural constraints such as low rank or graph smoothness. Graph-based and geometric deep-learning formulations use row and column relationships to regularize or learn localized patterns, while factorization improves scalability.
- Matrix completion: Recovering missing matrix entries from a small observed subset is ill-posed without constraints such as low rank.The low-rank assumption restricts variables to a smaller subspace.
- Matrix completion: Rank minimization is computationally intractable, motivating convex nuclear-norm relaxations and graph-smoothness constraints.The nuclear norm equals the sum of a matrix’s singular values and provides a convex relaxation.
- Geometric matrix completion: Graph-based completion represents user and item similarities with column and row graphs, respectively, and expresses smoothness through graph Laplacians and Dirichlet norms.The column graph captures user relationships, while the row graph captures item similarities.
- Factorized models: Factorization X = WH^⊤ reduces degrees of freedom from O(mn) to O(m + n) and enforces rank(WH^⊤) ≤ r by construction.W and H have dimensions m × r and n × r, with r ≪ min(m, n).
- Factorized models: Factorized graph models have linear rather than quadratic complexity but decouple regularization applied simultaneously to matrix rows and columns.This is the stated trade-off of the factorized formulation.
- Deep learning on graphs: Chebyshev polynomial graph filters avoid explicit Laplacian eigendecomposition, achieve O(n) cost on sparse graphs, and remain spatially localized.A degree-p filter affects the p-hop neighborhood through repeated Laplacian application.
3. Our approach
The approach formulates matrix completion as a learnable diffusion process, combining graph convolutions for spatial features with an LSTM for temporal rating dynamics. It uses full-matrix and factorized architectures, with the separable version reducing complexity for large matrices.
- Overall architecture: The model treats matrix completion as a learnable diffusion process with spatial feature extraction followed by recurrent temporal processing.The spatial component uses multi-graph or graph CNNs, while the temporal component uses an LSTM RNN.
- Multi-Graph CNNs: Spectral filters are represented with Chebyshev polynomial bases, avoiding explicit graph-Laplacian eigendecomposition and using a constant number of filter coefficients.The polynomial basis is parameterized by a coefficient matrix Θ with O(1) parameters.
- Multi-Graph CNNs: The Multi-Graph CNN applies row- and column-graph filters to an m×n matrix and produces q output feature channels for every matrix element.This full-matrix architecture produces an m×n×q tensor, but its application has O(mn) complexity.
- Separable convolution: The separable convolution applies one-dimensional graph convolutions independently to the factors W and H⊤ in the factorized matrix model.The resulting sRGCNN processes row and column factors separately before recurrent diffusion.
- Matrix diffusion with RNN: The RNN receives graph-convolution features for rows or columns and predicts updated scores during iterative diffusion.The factorized algorithm applies graph CNNs to H(t) and W(t), then applies an RNN to each resulting feature vector.
- Computational complexity: O(m + n) complexity is achieved by the factorized algorithm, compared with O(mn) for the full-matrix MGCNN algorithm.The separable design is presented as the option for large matrices because it processes rows and columns separately.
4. Results
Experiments on synthetic and real datasets show that the proposed recurrent graph CNNs achieve strong matrix-completion performance, including when only a users graph is available. The evaluation also examines convergence, learned spectral filters, parameter counts, and computational complexity.
- Experimental settings: Five standard datasets and four established methods were used as experimental baselines.The datasets were Synthetic, MovieLens, Flixster, Douban, and YahooMusic; baselines were MC, IMC, GMC, and GRALS.
- Experimental settings: The experiments use Chebyshev order p = 5, 32-dimensional features, 32-feature LSTM cells, and T = 10 diffusion steps.Factorized ranks are 15 for synthetic data and 10 for real datasets; hyperparameters were selected by cross-validation.
- Synthetic data: RGCNN achieved the best accuracy on the synthetic dataset, followed by sRGCNN.The experiments also visualize diffusion steps, convergence rates, and learned spectral filters.
- Synthetic data: With only the users graph available, sRGCNN remained applicable and the proposed approach performed best.In this setting, RGCNN cannot be applied, while sRGCNN applies one GCNN to factor H and leaves factor W free.
- Synthetic data: Figure 4 tracks matrix evolution for RGCNN and sRGCNN, with numbers indicating RMS error at different diffusion steps.RGCNN is shown for full matrix completion and sRGCNN for factorized matrix completion.
5. Conclusion
The paper presents a multi-graph convolutional architecture for matrix completion with low computational complexity and a constant number of degrees of freedom independent of matrix size. Experiments show that deep learning on graphs can outperform current state-of-the-art recommender-system methods.
- The proposed approach uses a specially designed multi-graph convolutional neural network for matrix completion.
- Its key advantages include low computational complexity and a constant number of degrees of freedom independent of matrix size.
- Experiments show that deep learning for matrix completion can beat current state-of-the-art recommender-system methods.
- The authors characterize the work as the first application of deep learning on graphs to this class of problems.