PaperlayerView exact revision on arXiv

Source-linked AI summary

UltraGCN: Ultra Simplification of Graph Convolutional Networks for Recommendation

Kelong Mao, Jieming Zhu, Xi Xiao, Biao Lu, Zhaowei Wang, Xiuqiang He

arXiv:2110.15114v2cs.IR

TL;DR

GCN message passing improves recommendation but slows convergence, especially on large graphs. UltraGCN skips explicit message passing by approximating infinite-layer convolutions with a constraint loss, and experiments report strong accuracy and efficiency.

  • Problem

    GCN message passing slows convergence, particularly for large-scale recommender systems, hindering their wider adoption.

  • Method

    UltraGCN skips explicit message passing and directly approximates the limit of infinite-layer graph convolutions through a constraint loss.

  • Results

    UltraGCN outperforms state-of-the-art collaborative-filtering models in accuracy and efficiency across four benchmark datasets.

  • Takeaways & Limitations

    UltraGCN provides a simple formulation with efficient training and flexible adjustment of different relationship importances.

  • Takeaways & Limitations

    Message-passing limitations identified for GCN-based collaborative filtering include questionable edge weights, inflexible relationship mixing, and over-smoothing with more layers.

Abstract

from arXiv · show

With the recent success of graph convolutional networks (GCNs), they have been widely applied for recommendation, and achieved impressive performance gains. The core of GCNs lies in its message passing mechanism to aggregate neighborhood information. However, we observed that message passing largely slows down the convergence of GCNs during training, especially for large-scale recommender systems, which hinders their wide adoption. LightGCN makes an early attempt to simplify GCNs for collaborative filtering by omitting feature transformations and nonlinear activations. In this paper, we take one step further to propose an ultra-simplified formulation of GCNs (dubbed UltraGCN), which skips infinite layers of message passing for efficient recommendation. Instead of explicit message passing, UltraGCN resorts to directly approximate the limit of infinite-layer graph convolutions via a constraint loss. Meanwhile, UltraGCN allows for more appropriate edge weight assignments and flexible adjustment of the relative importances among different types of relationships. This finally yields a simple yet effective UltraGCN model, which is easy to implement and efficient to train. Experimental results on four benchmark datasets show that UltraGCN not only outperforms the state-of-the-art GCN models but also achieves more than 10x speedup over LightGCN. Our source code will be available at https://reczoo.github.io/UltraGCN.

1 INTRODUCTION

GCN-based collaborative filtering improves recommendation by exploiting graph connectivity, but message passing makes these models difficult and slow to train on large graphs. UltraGCN addresses this challenge by removing explicit message passing and achieves strong effectiveness and efficiency.

  • GCN-based recommendation models exploit higher-order user-item connectivity and have achieved impressive performance gains.
  • Large-scale recommender systems make current GCN designs difficult to train because massive graphs create efficiency and scalability challenges.
  • Simplified GCN models can improve both performance and training efficiency over more complex designs.
  • 700 epochs: three-layer LightGCN takes more than 700 epochs to reach its best Amazon-Books result, making training unacceptable for industrial settings.
  • UltraGCN removes explicit message passing and directly approximates infinite-layer graph convolutions through a constraint loss.
  • Experiments on four benchmark datasets evaluate UltraGCN's effectiveness and efficiency.

2 MOTIVATION

The motivation centers on limitations of explicit message passing in GCN-based collaborative filtering. UltraGCN therefore skips message passing while retaining relationship modeling through directly trained representations.

  • 2.1 Revisiting GCN and LightGCN: Standard GCNs aggregate neighborhood information through message passing, while LightGCN removes feature transformations and nonlinear activations but retains propagation.
  • 2.1 Revisiting GCN and LightGCN: LightGCN stacks message-passing layers and uses the resulting embedding dot product for training and preference prediction.
  • 2.1 Revisiting GCN and LightGCN: Message passing captures user-item, item-item, and user-user collaborative signals in GCN-based recommendation.
  • 2.2 Limitations of Message Passing: The authors identify inappropriate edge weights, inflexible mixing of relationship types, and limitations from stacking more message-passing layers.
  • 2.2 Limitations of Message Passing: Recursive propagation can introduce noisy or uninformative relationships while failing to represent differing relationship importance.
  • 2.2 Limitations of Message Passing: UltraGCN questions explicit message passing and proposes an ultra-simplified GCN formulation that avoids it.

3 UltraGCN

UltraGCN replaces explicit message passing with constraint-based learning that approximates its infinite-layer convergence state. It assigns relationship-specific weights, selects item neighbors, and combines unified losses for efficient recommendation.

  • 3.1 Learning on User-Item Graph: UltraGCN approximates the convergence state of infinite-layer message passing without explicitly performing message passing.It minimizes the difference between a node representation and its neighborhood-aggregated counterpart using a constraint loss.
  • 3.1 Learning on User-Item Graph: The constraint loss uses positive and randomly sampled negative user-item pairs to capture arbitrarily high-order collaborative signals while mitigating over-smoothing.The loss coefficient is inversely proportional to user and item degrees with similar magnitudes.
  • 3.1.1 Optimization: UltraGCN combines the constraint loss with a binary cross-entropy objective for user-item link prediction.The base version depends only on user-item relationships, and a hyperparameter controls the relative importance of the two losses.
  • 3.2 Learning on Item-Item Graph: For item-item learning, UltraGCN builds a co-occurrence graph whose coefficient reflects co-occurrence while inversely weighting both item degrees.The method selects the top-K most similar items to retain sparse connections and training efficiency.
  • 3.2 Learning on Item-Item Graph: Each positive user-item pair produces K weighted positive pairs with similar items, allowing item-item relationships to be learned through a unified training formulation.The item-item loss extends UltraGCN, while hyperparameters adjust the relative importance of user-item and item-item relationships.
  • 3.3 Discussion: UltraGCN uses interpretable edge weights, separately customizable relationship learning, selected training pairs, and unified binary-cross-entropy losses to support fast convergence.Setting γ to 0 yields UltraGCN_Base, which learns only from the user-item graph.
  • 3.3.1 Model Analysis: The current UltraGCN version excludes user-user relationship modeling because user-user co-occurrence learning showed no noticeable improvement and may be better handled with social-network data.The authors leave social-network-based user-user modeling for future work.

4 EXPERIMENTS

Experiments across four benchmark datasets evaluate UltraGCN’s recommendation quality, training efficiency, and design choices. UltraGCN achieves the strongest reported performance while requiring substantially less training time than several comparison models.

  • 4.2 Performance Comparison: UltraGCN consistently yields the best performance across all four datasets.On Amazon-Book, it improves over DGCF by 61.4% in Recall@20 and 71.6% in NDCG@20; both improvements are statistically significant with p-value < 0.05.
  • 4.2 Performance Comparison: 61.4% and 71.6% relative improvements over DGCF are reported on Amazon-Book for Recall@20 and NDCG@20, respectively.The comparison uses the strongest GCN-based baseline, DGCF.
  • 4.3 Efficiency Comparison: Around 14x, 4x, and 4x speedups over LightGCN, LR-GCCF, and ENMF respectively are achieved, with UltraGCN requiring 75 epochs and 45 minutes to train.UltraGCN’s training speed per epoch is close to MF-BPR.
  • 4.3 Efficiency Comparison: With all models trained for 75 epochs, the other compared models achieve much worse performance than UltraGCN.This fixed-epoch comparison evaluates performance at the point when UltraGCN converges.
  • 4.4 Ablation Study: UltraGCN outperforms its simpler variants, while both user-item and item-item graph learning contribute to recommendation performance.UltraGCN(γ = 0) and UltraGCN(λ = 0) each outperform the variant with both components removed.
  • 4.4 Ablation Study: Using L_I performs better than using L′_I, especially when incorporating L_C.The authors attribute the larger gap to the unified objective facilitating training and improving performance.

5 RELATED WORK

GNN-based recommendation models exploit graph structure and higher-order connectivity, but their efficiency remains unsatisfactory for large-scale scenarios. Recent work therefore focuses on simplifying GNNs while preserving recommendation performance.

  • GC-MC, PinSage, and NGCF established graph-based approaches for recommendation across explicit matrix completion, industrial recommendation, and collaborative filtering.These methods differ in their use of rating types, random walks, graph convolutions, and interaction encoders.
  • GNN-based recommendation models achieve impressive performance, but their efficiency remains unsatisfactory in large-scale recommendation scenarios.Improving efficiency while retaining performance is identified as an active research problem.
  • Recent studies simplify GNNs for recommendation and related representation-learning tasks to address efficiency concerns.The related work includes fixed-point approaches and simplified GCN formulations.

6 CONCLUSION

UltraGCN is an ultra-simplified GCN formulation that skips explicit message passing and approximates its infinite-layer limit. Experiments report improvements over state-of-the-art collaborative-filtering models in both accuracy and efficiency.

  • UltraGCN skips explicit message passing and directly approximates the limit of infinite message-passing layers.The formulation is designed for recommendation efficiency.
  • Extensive experiments demonstrate that UltraGCN improves over state-of-the-art collaborative-filtering models in both accuracy and efficiency.

8 APPENDIX

UltraGCN was additionally compared with recent state-of-the-art collaborative-filtering models using each paper’s dataset and evaluation protocol. Table 6 reports the corresponding performance comparison.

  • UltraGCN was evaluated against NBPO, BGCF, SCF, LCFN, and SGL-ED using the same dataset and evaluation protocol provided by each referenced paper.The reported results were duplicated from the referenced papers for consistency.
  • Table 6 presents a performance comparison between UltraGCN and additional collaborative-filtering models.
Loading 2110.15114v2…