PaperlayerView exact revision on arXiv

Source-linked AI summary

Inductive Matrix Completion Based on Graph Neural Networks

Muhan Zhang, Yixin Chen

arXiv:1904.12058v3cs.IRcs.LGstat.ML

TL;DR

Matrix completion is usually transductive, and inductive methods often require side information that may be unavailable. IGMC addresses this by training a GNN on local rating-graph subgraphs, achieving competitive performance and transfer across tasks without retraining.

  • Problem

    Matrix factorization is transductive, while inductive matrix completion commonly relies on user and item content that may be unavailable or low quality.

  • Method

    IGMC constructs a labeled bipartite graph from the rating matrix, extracts local enclosing subgraphs, and trains a GNN to predict their ratings.

  • Results

    IGMC achieves highly competitive performance with state-of-the-art baselines, transfers to new tasks without retraining, and is more robust on sparse rating matrices.

  • Takeaways & Limitations

    Local graph patterns around user-item pairs can effectively predict ratings, allowing inductive completion without side information and supporting transfer to new recommendation tasks.

  • Takeaways & Limitations

    IGMC has higher complexity than a node-level GNN because it processes enclosing subgraphs for target ratings, although subsampling can reduce this cost.

Abstract

from arXiv · show

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.

1 INTRODUCTION

Traditional matrix completion is transductive, while inductive approaches usually depend on user and item content that may be unavailable. IGMC instead learns rating-prediction patterns from local bipartite-graph structure without content and generalizes to unseen entities and tasks.

  • Matrix factorization learns user and item embeddings that do not generalize to unseen rows or columns without retraining.
  • Inductive matrix completion uses user and item content features, but performance depends on the availability and quality of that content.
  • IGMC extracts h-hop enclosing subgraphs around user-item pairs, maps them to ratings with a GNN, and uses the trained model to complete missing entries.
  • IGMC converts matrix completion into labeled-link prediction on a rating-derived bipartite graph and learns local graph patterns with a GNN.
  • IGMC does not address extreme cold start because an unseen user-item pair must have neighboring interactions for its enclosing subgraph to exist.
  • IGMC achieves the smallest RMSE on four of five benchmark datasets without content and can transfer from MovieLens to Douban without retraining.

2 RELATED WORK

Related work applies GNNs and learned graph patterns to graph and matrix-completion problems, while IGMC extracts local enclosing subgraphs for individual rating predictions rather than processing the entire matrix.

  • Graph neural networks: Node-level GNNs pass messages between neighboring nodes to encode local substructures, whereas graph-level GNNs produce representations for entire graphs.
  • GNNs for matrix completion: Existing GNN matrix-completion models extract user and item features from neighboring networks or directly from the user-item bipartite graph.
  • GNNs for matrix completion: Exchangeable matrix layers achieve inductive completion without content through permutation-equivariant matrix operations, but process the entire rating matrix.
  • Enclosing subgraph extraction: IGMC extracts an h-hop enclosing subgraph for each training pair, removes the target edge, and feeds the resulting subgraph to a GNN for rating regression.
  • GNNs for matrix completion: Unlike whole-matrix processing, IGMC uses local subgraphs to avoid scalability concerns and predict individual ratings.
  • Link prediction based on graph patterns: Learned graph-pattern methods extend heuristic link prediction by automatically learning structure features from subgraphs with neural networks and GNNs.

3 INDUCTIVE GRAPH-BASED MATRIX COMPLETION (IGMC)

IGMC represents the rating matrix as an edge-labeled bipartite graph and predicts ratings from locally extracted enclosing subgraphs using a graph-level GNN. Its training combines rating-error minimization with adjacent-rating regularization that incorporates rating order and supports infrequent ratings.

  • Graph construction: IGMC constructs an undirected bipartite graph whose user-item edges carry the corresponding ratings as edge types.Users represent matrix rows, items represent columns, and neighbors can be grouped by rating type.
  • Enclosing subgraph extraction: For each observed or test user-item pair, IGMC extracts an h-hop enclosing subgraph and removes the target training edge before prediction.The same extraction-and-prediction procedure supports training and testing pairs.
  • Node labeling: Node labeling marks target nodes and distinguishes user-type from item-type nodes, with labels determined independently within each enclosing subgraph.One-hot encodings of these labels provide initial node features and support predictions on subgraphs from different bipartite graphs.
  • Graph neural network architecture: A graph-level GNN maps each enclosing subgraph to a rating, contrasting with approaches that compute embeddings for the entire bipartite graph.IGMC uses relational message passing to learn patterns associated with different rating types, including average ratings and paths connecting target nodes.
  • Graph neural network architecture: The graph representation concatenates the final representations of only the target user and item, which empirically outperforms summing and other pooling layers on the matrix-completion tasks.The design emphasizes the target nodes over contextual nodes.
  • Model training: Training minimizes mean squared error and adds adjacent rating regularization, constraining neighboring rating-specific parameters while transferring knowledge to infrequent ratings.The regularizer accounts for rating order; λ controls its trade-off against the MSE loss, while alternative magnitude-and-order models remain future work.

4 GRAPH-LEVEL GNN VS. NODE-LEVEL GNN

IGMC uses a graph-level GNN on each target pair’s enclosing subgraph rather than node embeddings learned over the entire bipartite graph. This improves local structural discrimination but incurs higher computational complexity, which subsampling can reduce.

  • IGMC maps the enclosing subgraph around each target user-item pair directly to its rating with a graph-level GNN.
  • Node-level approaches learn user and item embeddings on the entire bipartite graph before predicting ratings, unlike IGMC’s subgraph-based mapping.
  • Graph-level GNNs can distinguish local subgraph patterns through repeated message passing because computation remains confined within explicit subgraph boundaries.
  • Processing every enclosing subgraph has complexity O(K|E|) per message-passing round, compared with O(|E|) for one node-level round on the full graph.Here, |E| is the number of bipartite-graph edges and K bounds edges across enclosing subgraphs.
  • Subsampling can restrict K to reduce the computational complexity of IGMC.

5 EXPERIMENTS

Experiments evaluate IGMC across five benchmark datasets, compare it with transductive and inductive baselines, and test transferability, sparsity robustness, and learned graph-pattern behavior.

  • 5.1 FLIXSTER, DOUBAN AND YAHOOMUSIC: IGMC achieves the smallest RMSEs on Flixster, Douban, and YahooMusic without content, outperforming compared transductive and inductive baselines.The comparison includes GRALS, sRGCNN, GC-MC, F-EAE, PinSage, and IGC-MC.
  • 5.2 ML-100K AND ML-1M: IGMC achieves the best performance on ML-100K, alongside GC-MC despite using no content and remaining inductive while GC-MC is transductive.The MovieLens experiments also evaluate ML-1M against additional matrix-completion baselines.
  • 5.3 SPARSE RATING MATRIX ANALYSIS: Below a 20% sparsity ratio, IGMC outperforms GC-MC on ML-1M, with a larger advantage under extreme sparsity.The models are trained on randomly retained fractions of the original training ratings and evaluated on the original test set.
  • 5.4 TRANSFER LEARNING: An IGMC model trained on ML-100K transfers to Flixster, Douban, and YahooMusic, outperforming other inductive models and some dataset-specific baselines.Rating scales and edge types are adjusted for the transferred datasets before prediction.
  • 5.6 VISUALIZATION: High- and low-predicted-rating enclosing subgraphs exhibit substantially different patterns, including differences in user and item average ratings.High-score subgraphs typically have high user and item average ratings, whereas low-score subgraphs often contain mixed ratings and low user average ratings.

6 CONCLUSION

IGMC replaces transductive latent features with inductively learned local graph patterns, without requiring user or item content. It achieves competitive baseline performance and can transfer to new tasks without retraining.

  • IGMC learns local graph patterns related to ratings using graph neural networks instead of transductive latent features.
  • IGMC does not rely on user or item side information, unlike previous inductive matrix completion methods.
  • IGMC achieves highly competitive performance compared to state-of-the-art baselines.
  • IGMC can transfer to new tasks without retraining, which is useful for recommendation tasks with few training data.

A ABLATION STUDIES

The ablation experiments examine IGMC’s pooling layer, adjacent rating regularization (ARR), and content incorporation. Results indicate that target-aware pooling is important, ARR provides dataset-dependent gains, and adding content does not consistently improve performance.

  • The proposed pooling layer substantially outperforms standard SumPooling by distinguishing the target user and item from context nodes.SumPooling assigns equal importance to all nodes in each subgraph.
  • Disabling ARR causes a 0.003 performance drop on ML-100K but has seemingly no effect on the other three datasets.The authors suggest ARR may help more on large, dense enclosing subgraphs, while noting that λ was tuned only on ML-100K and fixed at 0.001 elsewhere.
  • Adding content does not improve ML-100K performance and often hurts performance on the other datasets.For Flixster, Douban, and YahooMusic, their content graphs add little to IGMC’s already-exploited user–item graph structure, while 3000-dimensional features may also contribute to the issue.
  • After introducing ARR and retuning hyperparameters, ML-100K RMSE without content reaches 0.905, and adding content no longer helps.The authors hypothesize that better graph-structure modeling reduces the benefits of content.
  • Content concatenation may be ineffective because it combines target features only with the final GNN representation, missing early interactions between content and graph structure.The authors identify this incorporation strategy as another possible reason content is not useful in IGMC.
Loading 1904.12058v3…