Inductive Matrix Completion Based on Graph Neural Networks

Muhan Zhang, Yixin Chen

Overview

Inductive Graph-based Matrix Completion (IGMC) is a novel framework that performs matrix completion—the core task of modern recommender systems—using only the graph structure of user-item interactions. Unlike traditional methods, IGMC is fully inductive, meaning it can predict ratings for new users and items without requiring model retraining. Remarkably, it achieves state-of-the-art performance without relying on any side information, such as user profiles or movie genres.

The Problem: Transductive Bottlenecks

Most recommender systems rely on Matrix Factorization (MF), which is inherently transductive. In MF, the model learns a fixed "latent vector" (or embedding) for every specific user and item ID present in the training data. If a new user joins the platform, the model lacks an embedding for them and must be retrained from scratch—a major computational bottleneck for dynamic, real-world systems.

To make these models inductive (capable of handling unseen nodes), researchers typically turn to side information—metadata like a user's age or a movie's genre. However, high-quality metadata is often unavailable, incomplete, or expensive to collect. The authors of this paper pose a critical question: Can we build an inductive recommender system using only the rating matrix itself?

The IGMC Approach

The authors treat matrix completion as a link prediction problem on a bipartite graph, where users and items are nodes, and ratings are labeled edges. Their approach, IGMC, abandons ID-specific embeddings in favor of learning local graph patterns.

IGMC Framework

The framework consists of four main steps:

  1. Enclosing Subgraph Extraction: For a target (user, item) pair, the model extracts a local $h$-hop "enclosing subgraph." This subgraph contains the target pair and their immediate neighbors (e.g., other movies the user rated and other users who rated the target movie).
  2. Node Labeling: To help the Graph Neural Network (GNN) understand the local structure, nodes are assigned labels based on their role. The target user is labeled 0, the target item is labeled 1, and neighbors are labeled based on their distance and type. This allows the model to distinguish "who is who" within the local context without relying on global IDs.
  3. GNN Architecture: IGMC utilizes a Relational Graph Convolutional Network (R-GCN). Because ratings (e.g., 1-5 stars) are discrete, each rating value is treated as a different edge type. To ensure the model understands ordinal relationships (e.g., a 4-star rating is closer to 5 stars than 1 star), the authors introduce Adjacent Rating Regularization (ARR), which penalizes large differences between the parameter matrices of adjacent rating levels.
  4. Rating Prediction: The final representations of the target user and item are concatenated and passed through a Multi-Layer Perceptron (MLP) to output a predicted scalar rating.

Key Insights: Why It Works

  • Local is Enough: The paper demonstrates that "long-range dependencies" (looking at users many hops away) are not strictly necessary for good recommendations. A 1-hop or 2-hop neighborhood captures sufficient collaborative filtering signals to accurately predict a rating.
  • Patterns over IDs: By focusing on the shape of the local graph rather than the identity of the nodes, the model learns generalizable heuristics (e.g., "Users who liked similar things as you also liked this movie").
  • Structural Features vs. Latent Features: Traditional GNNs for recommendation often use node-level embeddings. IGMC uses graph-level representations. This structural focus is the "secret sauce" that makes it inductive; the model doesn't care who the user is, only how they are connected to the item.

Key Results

The model was evaluated on standard benchmarks including Flixster, Douban, YahooMusic, and MovieLens datasets.

Performance Comparison on Flixster, Douban, and YahooMusic
  • Superior Performance: IGMC achieved the lowest Root Mean Square Error (RMSE) on Flixster (0.872), Douban (0.721), and YahooMusic (19.1), successfully beating state-of-the-art transductive models that did use side information.
  • Robustness to Sparsity: On MovieLens-1M, when training data was drastically reduced to just 0.1%, IGMC significantly outperformed the leading transductive baseline (GC-MC), proving its efficacy in "cold" or sparse scenarios.
  • Impressive Transfer Learning: Because IGMC learns structural patterns rather than ID embeddings, it can transfer across datasets. A model trained on MovieLens-100K was tested directly on Douban (a completely different movie site) and achieved an RMSE of 0.759, outperforming several baselines that were trained natively on Douban data.

Limitations and Future Work

While highly effective, IGMC has limitations. Extracting a unique subgraph for every single user-item pair is more computationally expensive than standard node-level GNNs. Scaling this to billions of edges requires careful subsampling and optimization. Furthermore, while IGMC is inductive, it still requires a new user to have at least some interactions to form a subgraph. It cannot predict for a user with absolutely zero ratings (the "extreme cold start" problem), where side information remains necessary. Future directions include optimizing subgraph extraction for production-scale systems and exploring hybrid models that seamlessly integrate graph structure with available side information.

Summary updated

Abstract

We propose an inductive matrix completion model without using side information. By factorizing the (rating) matrix into the product of low-dimensional latent embeddings of rows (users) and columns (items), a majority of existing matrix completion methods are transductive, since the learned embeddings cannot generalize to unseen rows/columns or to new matrices. To make matrix completion inductive, most previous works use content (side information), such as user's age or movie's genre, to make predictions. However, high-quality content is not always available, and can be hard to extract. Under the extreme setting where not any side information is available other than the matrix to complete, can we still learn an inductive matrix completion model? In this paper, we propose an Inductive Graph-based Matrix Completion (IGMC) model to address this problem. IGMC trains a graph neural network (GNN) based purely on 1-hop subgraphs around (user, item) pairs generated from the rating matrix and maps these subgraphs to their corresponding ratings. It achieves highly competitive performance with state-of-the-art transductive baselines. In addition, IGMC is inductive -- it can generalize to users/items unseen during the training (given that their interactions exist), and can even transfer to new tasks. Our transfer learning experiments show that a model trained out of the MovieLens dataset can be directly used to predict Douban movie ratings with surprisingly good performance. Our work demonstrates that: 1) it is possible to train inductive matrix completion models without using side information while achieving similar or better performances than state-of-the-art transductive methods; 2) local graph patterns around a (user, item) pair are effective predictors of the rating this user gives to the item; and 3) Long-range dependencies might not be necessary for modeling recommender systems.
BibTeX
@inproceedings{zhang2020inductive,
  author = {Muhan Zhang and Yixin Chen},
  title = {{Inductive Matrix Completion Based on Graph Neural Networks}},
  booktitle = {International Conference on Learning Representations},
  year = {2020},
  url = {https://openreview.net/forum?id=OOxqSvG7niB},
}
Figure