PaperlayerView exact revision on arXiv

Source-linked AI summary

Neural Graph Collaborative Filtering

Xiang Wang, Xiangnan He, Meng Wang, Fuli Feng, Tat-Seng Chua

arXiv:1905.08108v2cs.IRcs.LGcs.SI

TL;DR

Existing recommender methods often learn embeddings from descriptive features without explicitly encoding collaborative signals in user-item interactions. NGCF propagates embeddings over the user-item graph to model high-order connectivity, achieving state-of-the-art performance across three million-size datasets.

  • Problem

    Existing methods typically learn embeddings from descriptive features without explicitly encoding the collaborative signal in user-item interactions.

  • Method

    NGCF explicitly encodes collaborative signal by propagating user and item embeddings over high-order connectivities in the user-item graph.

  • Results

    NGCF demonstrates state-of-the-art performance and improved embedding quality in extensive experiments on three million-size datasets.

  • Takeaways & Limitations

    Embedding propagation benefits representation learning, particularly for relatively inactive users, by exploiting high-order connectivity in the interaction graph.

  • Takeaways & Limitations

    NGCF uses only an inner-product interaction function, leaving more complicated neural interaction functions for future work.

Abstract

from arXiv · show

Learning vector representations (aka. embeddings) of users and items lies at the core of modern recommender systems. Ranging from early matrix factorization to recently emerged deep learning based methods, existing efforts typically obtain a user's (or an item's) embedding by mapping from pre-existing features that describe the user (or the item), such as ID and attributes. We argue that an inherent drawback of such methods is that, the collaborative signal, which is latent in user-item interactions, is not encoded in the embedding process. As such, the resultant embeddings may not be sufficient to capture the collaborative filtering effect. In this work, we propose to integrate the user-item interactions -- more specifically the bipartite graph structure -- into the embedding process. We develop a new recommendation framework Neural Graph Collaborative Filtering (NGCF), which exploits the user-item graph structure by propagating embeddings on it. This leads to the expressive modeling of high-order connectivity in user-item graph, effectively injecting the collaborative signal into the embedding process in an explicit manner. We conduct extensive experiments on three public benchmarks, demonstrating significant improvements over several state-of-the-art models like HOP-Rec and Collaborative Memory Network. Further analysis verifies the importance of embedding propagation for learning better user and item representations, justifying the rationality and effectiveness of NGCF. Codes are available at https://github.com/xiangwang1223/neural_graph_collaborative_filtering.

1 INTRODUCTION

The paper argues that conventional collaborative-filtering embeddings omit collaborative signals latent in user-item interactions, leaving interaction functions to compensate for insufficient representations. It proposes NGCF, which explicitly encodes high-order connectivity through recursive embedding propagation on the interaction graph and evaluates the approach on three million-size datasets.

  • Problem: Existing embedding methods rely mainly on descriptive features such as IDs and attributes, without explicitly encoding collaborative signals in user-item interactions.This omission can produce embeddings insufficient for capturing collaborative filtering effects.
  • Motivation: Large-scale interaction data makes it difficult to distill collaborative signals, motivating the use of high-order connectivity in the interaction graph.High-order paths encode behavioral similarity and item-interest relationships through multi-step user-item connections.
  • Present Work: NGCF models high-order connectivity directly in the embedding function by recursively propagating embeddings over the user-item graph.The method uses a neural network inspired by graph neural networks rather than expanding the interaction graph as a tree.
  • Experiments: The authors conduct extensive empirical studies on three million-size datasets to evaluate NGCF's effectiveness and performance.The introduction states that these studies demonstrate state-of-the-art performance and the effectiveness of embedding propagation.
  • Present Work: Unlike HOP-Rec, which uses high-order connectivity only to enrich training data while retaining matrix factorization for prediction, NGCF integrates it into the prediction model.The distinction is whether high-order connectivity modifies training data or the predictive embedding mechanism itself.

2 METHODOLOGY

NGCF comprises an embedding layer, multiple embedding propagation layers, and a prediction layer. These components initialize embeddings, inject high-order connectivity relations, and aggregate refined embeddings to output a user-item affinity score.

  • NGCF uses an embedding layer to initialize user and item embeddings.
  • Multiple embedding propagation layers refine embeddings by injecting high-order connectivity relations.
  • A prediction layer aggregates refined embeddings from different propagation layers and outputs a user-item affinity score.

2.1 Embedding Layer

NGCF initializes users and items with trainable ID embedding vectors, then refines these representations by propagating them over the user-item interaction graph. Outputs from multiple propagation layers are concatenated for final prediction.

  • Embedding Layer: Each user u and item i is represented by an embedding vector in R^d, where d denotes the embedding size.These vectors form an embedding look-up table parameterized for users and items.
  • Embedding Layer: The embedding table provides the initial user and item states and is optimized end-to-end.Unlike MF and neural collaborative filtering, NGCF does not directly feed these ID embeddings into the interaction layer.
  • Embedding Layer: NGCF refines embeddings by propagating them on the user-item interaction graph before prediction.Multiple propagation layers refine user and item representations, whose outputs are concatenated to form the final prediction.

2.2 Embedding Propagation Layers

NGCF propagates embeddings across connected users and items through message construction and aggregation, encoding interaction affinity and retaining self-information. Stacking layers extends this process to multi-hop neighborhoods, explicitly injecting high-order collaborative signals into representations.

  • Message Construction: Embedding propagation constructs messages from connected item-user embeddings, weighting edge contributions with p_ui and encoding their element-wise interaction.The message function uses trainable matrices and makes propagation dependent on the affinity between e_i and e_u.
  • Message Aggregation: Message aggregation combines neighbor messages with a self-connection, using LeakyReLU while retaining the user’s original feature information.The same propagation process analogously refines item representations from connected users.
  • Message Aggregation: A single propagation layer explicitly exploits first-order user-item connectivity to relate user and item representations.The layer refines each node using information from its directly connected neighbors.
  • Multi-layer Propagation: Stacking l embedding propagation layers lets users and items receive messages from l-hop neighbors, capturing high-order connectivity for relevance estimation.Messages generated at earlier layers preserve information from progressively more distant neighbors.
  • Multi-layer Propagation: The multi-layer process captures paths such as u1 ← i2 ← u2 ← i4 and injects their collaborative signal into representation learning.The message from i4 is explicitly encoded in the third-layer representation of u1.
  • Propagation Rule in Matrix Form: The matrix-form propagation rule simultaneously updates all user and item representations efficiently, avoiding node sampling for large-scale graphs.The formulation uses the user-item graph’s Laplacian matrix and supports batch implementation.

2.3 Model Prediction

NGCF concatenates representations learned across propagation layers to form final user and item embeddings, enriching initial embeddings while controlling propagation depth. It then estimates user preference with an inner product, leaving more complex interaction functions for future work.

  • Embedding construction: NGCF concatenates representations from different propagation layers to form the final user and item embeddings.Different layers capture messages passed over different connections and therefore contribute differently to reflecting preference.
  • Embedding construction: Concatenation enriches initial embeddings through propagation while allowing the propagation range to be controlled by adjusting L.Other aggregators, including weighted average, max pooling, and LSTM, can combine different connectivity orders but imply different assumptions.
  • Preference prediction: The model estimates a user’s preference for a target item using the inner product of the final user and item embeddings.The framework emphasizes embedding-function learning and uses this simple interaction function rather than more complicated neural network-based alternatives.

2.4 Optimization

NGCF is optimized with pairwise BPR loss, using mini-batch Adam to update parameters after propagating embeddings through the user-item graph. Regularization relies on L2 penalties and training-only message and node dropout to reduce overfitting and improve robustness.

  • Optimization: NGCF optimizes pairwise BPR loss, assigning higher prediction values to observed interactions than to unobserved interactions.BPR models the relative order between observed and unobserved user-item interactions.
  • Optimization: L2 regularization controls model complexity and helps prevent overfitting.The regularization strength is denoted by λ.
  • Optimization: Mini-batch Adam updates model parameters from gradients computed on randomly sampled triples after L propagation steps.The propagated representations are established as [e(0), · · · , e(L)] for each sampled batch.
  • Optimization: NGCF introduces few additional parameters because propagation-layer embeddings derive from the initial lookup table through graph transformations and weight matrices.The model uses two weight matrices per propagation layer while modeling high-order connectivity.
  • Optimization: NGCF uses message dropout and node dropout during training to reduce overfitting.Message dropout randomly removes propagated outgoing messages, whereas node dropout reduces the influence of particular users or items; dropout is disabled during testing.

2.5 Discussions

NGCF generalizes SVD++ and FISM as special cases under specific propagation settings. Its training complexity depends on layer-wise graph propagation, and empirically NGCF is slower than MF on Gowalla.

  • Model Generalization: SVD++ is a special case of NGCF with one propagation layer, disabling the transformation matrix and nonlinear activation.The resulting simplified model is termed NGCF-SVD.
  • Model Generalization: FISM is also a special case of NGCF when p′_iu in Equation (12) is set to 0.SVD++ is exactly recovered by setting p′_ui and p′_iu to 1/|N_u| and 0, respectively.
  • Time Complexity: The l-th propagation layer has matrix-multiplication complexity O(|R+|d_ld_l−1), while prediction uses only inner products.Here, |R+| is the number of nonzero entries in the Laplacian matrix, and d_l and d_l−1 are current and previous transformation sizes.
  • Empirical Cost: On Gowalla, MF and NGCF require around 20s and 80s per training epoch, respectively, and 80s and 260s for inference.These timings use the same experimental settings described in Section 4.

3 RELATED WORK

Related work spans model-based, graph-based, and graph neural network-based collaborative filtering. NGCF differs by explicitly propagating embeddings over the user-item graph to capture high-order collaborative signals.

  • Model-based collaborative filtering: Model-based methods embed users and items from IDs or side information, then reconstruct interactions through vector similarity.Matrix factorization uses inner products between user and item embeddings, while other methods incorporate item content, social relations, item relations, or reviews.
  • Model-based collaborative filtering: These embedding functions may inadequately capture collaborative-filtering signals because interactions are encoded only implicitly.The embedding function maps descriptive features to vectors, while the interaction function measures similarity between those vectors.
  • Graph-based collaborative filtering: Graph-based methods propagate interaction labels or enrich user histories with multi-hop connected items to infer preferences.ItemRank and BiRank use label propagation, whereas HOP-Rec combines random walks with matrix factorization and Bayesian personalized ranking.
  • Graph neural network-based methods: Existing graph-convolution methods differ from NGCF in graph scope or connectivity depth: GC-MC uses one user-item layer, while PinSage uses item-item layers.NGCF instead devises a specialized convolution operation on the user-item interaction graph to exploit collaborative signals in high-order connectivities.

4 EXPERIMENTS · 4.1 Dataset Description · 4.2 Experimental Settings

NGCF is evaluated on three real-world recommendation datasets through comparisons with established collaborative-filtering methods and systematic experimental protocols. The study examines performance, hyperparameter effects, and the benefits of high-order connectivity and embedding propagation.

  • 4 EXPERIMENTS: Experiments on three real-world datasets evaluate NGCF, especially its embedding propagation layer, through three research questions about performance, hyperparameters, and high-order connectivity.The questions address comparisons with state-of-the-art collaborative-filtering methods, settings such as layer depth and dropout, and representation benefits from high-order connections.
  • 4.1 Dataset Description: The benchmark datasets are Gowalla, Yelp2018∗, and Amazon-book, which differ in domain, size, and sparsity.Gowalla is a check-in dataset filtered with a 10-core setting that retains users and items having at least ten interactions.
  • 4.1 Dataset Description: The experiments rerun methods under the revised Yelp2018 setting after filtering cold-start items from the testing set.The enriched trained data is described as a regularizer to the original training.
  • 4.1 Dataset Description: For each dataset, 80% of each user’s historical interactions form training data, while the remainder is used for testing and 10% of training interactions for validation.Observed interactions are positive instances, paired during training with one negatively sampled item the user has not previously consumed.
  • 4.2.1 Evaluation Metrics: Evaluation treats every unobserved test item as negative and scores each user over all items except training positives using recall@K and ndcg@K with K = 20.The reported metrics are averaged across all users in the test set.
  • 4.2.2 Baselines: NGCF is compared against matrix factorization, NeuMF, and graph-based collaborative-filtering methods to demonstrate its effectiveness.MF uses BPR loss and direct interactions, whereas NeuMF models nonlinear user-item feature interactions with multilayer neural architectures.
  • 4.2.2 Baselines: GC-MC uses a GCN encoder with only first-order neighbors, employing one graph convolution layer whose hidden dimension equals the embedding size.The experimental description also notes that NGCF uses two graph convolution layers as suggested in prior work.
  • 4.2.2 Baselines: All models use embedding size 64; models other than HOP-Rec are optimized with Adam and batch size 1024.HOP-Rec random-walk steps and learning rate are searched separately, while other hyperparameters are tuned by grid search.

4.3 Performance Comparison (RQ1) · 4.4 Study of NGCF (RQ2)

NGCF outperforms baselines, particularly for sparse users, by explicitly exploiting high-order connectivity. Ablations show that propagation depth, interaction-aware messages, node dropout, and propagation-enabled optimization materially affect performance and convergence.

  • 4.3.1 Overall Comparison.: NeuMF consistently outperforms MF, while GC-MC improves over both by incorporating first-order neighbors into representation learning.MF’s inner product is insufficient for complex user-item relations, whereas NeuMF captures nonlinear feature interactions; neither explicitly models graph connectivity.
  • 4.3.2 Performance Comparison w.r.t. Interaction Sparsity Levels.: User groups are divided by interaction counts, with Gowalla thresholds below 24, 50, 117, and 1014 interactions per user.Experiments evaluate ndcg@20 across Gowalla, Yelp2018∗, and Amazon-Book, with recall@20 showing a similar trend.
  • 4.3.2 Performance Comparison w.r.t. Interaction Sparsity Levels.: NGCF and HOP-Rec consistently outperform all other baselines across user groups, showing that high-order connectivity improves representations for inactive users.The collaborative signal can therefore be captured more effectively under sparse interaction conditions.
  • 4.4 Study of NGCF (RQ2): The study evaluates propagation depth, the Laplacian discounting factor pui, node dropout, message dropout, and NGCF’s training process.These analyses target how embedding propagation and regularization influence recommendation performance and optimization behavior.
  • 4.4.1 Effect of Layer Numbers.: NGCF-2 and NGCF-3 consistently improve over NGCF-1 across recommendation cases by modeling second- and third-order connectivity.NGCF-4 overfits on Yelp2018∗, while producing only marginal improvements on the other two datasets.
  • 4.4.2 Effect of Embedding Propagation Layer and Layer-Aggregation Mechanism.: NGCF-1 is consistently superior to NGCF-1PinSage, NGCF-1GC-MC, and NGCF-1SVD++, supporting interaction-aware message propagation.The element-wise interaction eu ⊙ei makes messages depend on node affinity and functions like an attention mechanism.
  • 4.4.3 Effect of Dropout.: 0.1514 is the highest Gowalla recall@20 achieved with node dropout p2=0.2, exceeding message dropout’s 0.1506.Node dropout performs better because removing outgoing messages from users and items improves robustness to edge and node effects.
  • 4.4.4 Test Performance w.r.t. Epoch.: NGCF converges faster than MF on all three datasets when comparing test recall across epochs.Embedding propagation brings indirectly connected users and items into mini-batch optimization, indicating greater model capacity.

4.5 Effect of High-order Connectivity (RQ3)

NGCF’s embedding propagation reflects user-item connectivity in the embedding space, with three propagation layers producing discernible clusters of items consumed by the same users. This effect is visualized for six Gowalla users and their relevant test-set items by comparing MF (NGCF-0) with NGCF-3.

  • Experimental setup: The analysis examines how embedding-propagation depth influences representations for six randomly selected Gowalla users and their relevant items.The comparison focuses on representations learned at different NGCF depths.
  • Experimental setup: The visualization compares MF, or NGCF-0, with NGCF-3 using items from the test set that were not paired with users during training.This setup evaluates whether learned representations reflect connectivity beyond observed training pairs.
  • Findings: NGCF-3 places connected users and items near one another in the embedding space, and items consumed by the same users form discernible clusters.The clustering is indicated by points with the same colors, representing items consumed by the same users.

5 CONCLUSION AND FUTURE WORK

NGCF incorporates collaborative signal into model-based collaborative filtering by propagating embeddings over high-order user-item graph connectivities. The work also motivates future research on integrating additional structural information into recommendation.

  • Conclusion: NGCF explicitly incorporates collaborative signal into model-based collaborative filtering through an embedding propagation layer over high-order user-item graph connectivities.The layer enables user and item embeddings to interact and harvest collaborative signal.
  • Future Work: The work presents an initial use of message passing to exploit structural knowledge in model-based collaborative filtering and opens new research possibilities.
  • Future Work: Future structural signals include cross features, item knowledge graphs, and social networks for understanding user behaviors.Combining an item knowledge graph with the user-item graph can establish knowledge-aware user-item connectivities that help unveil users’ item-choice processes.
Loading 1905.08108v2…