CDRec: Cayley-Dickson Recommender

Anchen Li, Bo Yang, Huan Huo, Farookh Khadeer Hussain

TL;DR

This paper introduces CDRec, a novel recommendation framework that leverages Cayley-Dickson algebras to represent users and items in high-dimensional hypercomplex spaces. By combining this algebraic construction with graph convolutional networks (GCNs), CDRec effectively models complex user-item relationships, achieving state-of-the-art performance on real-world recommendation tasks.

What Problem Does This Paper Address?

Traditional recommendation systems, particularly those based on collaborative filtering (CF), primarily operate within the realm of real numbers. While effective, this approach may overlook the richer representational capacity offered by alternative algebraic systems. Recent research has begun exploring hypercomplex spaces (e.g., complex numbers, quaternions) for recommendation, recognizing that these multi-component structures can better capture intricate user-item interactions. However, existing hypercomplex recommendation models are often limited to lower-dimensional algebras and may not fully exploit the potential of higher-dimensional spaces. This paper addresses this gap by proposing a framework that systematically utilizes high-dimensional Cayley-Dickson algebras and integrates them with powerful GCN techniques for enhanced recommendation.

Methods

The core of CDRec lies in two main innovations:

  • Cayley-Dickson Construction: This recursive process is used to define a sequence of hypercomplex algebras, each doubling the dimension of the previous one. This allows CDRec to explore a wide range of high-dimensional hypercomplex spaces, from complex numbers (2D) to trigintaduonions (32D).
  • Hypercomplex Graph Convolution (HGC) Layer: CDRec employs a novel GCN layer designed to operate within these hypercomplex spaces. This layer aggregates neighborhood information by combining a linear aggregator (inspired by standard GCNs) and a hypercomplex interaction aggregator. The interaction aggregator specifically uses hypercomplex multiplication to capture intricate relationships between components of user and item embeddings, which is a key advantage over real-valued multiplication. Notably, CDRec omits traditional transformation matrices and activation functions within its GCN layers, a design choice supported by recent findings in GCN-based recommenders.

The framework consists of an embedding layer to initialize hypercomplex user and item representations, followed by L HGC layers to refine these embeddings, and finally a prediction layer that outputs the user-item preference score.

Datasets

The authors evaluated CDRec on three real-world datasets:

  • Douban Book: Book recommendation data.
  • Douban Movie: Movie recommendation data.
  • KKBox: Music recommendation data.

These datasets are standard benchmarks in the recommendation community. No new datasets were introduced.

Key Insights and Ideas

  • High-Dimensional Hypercomplex Spaces Offer Superior Representation: The paper strongly suggests that moving beyond 2D (complex) or 4D (quaternion) spaces to higher-dimensional Cayley-Dickson algebras can significantly enhance recommendation performance.
  • Hypercomplex Multiplication Captures Richer Interactions: Unlike real-valued multiplication, hypercomplex multiplication explicitly models the interplay between different components of embeddings, leading to more nuanced understanding of user-item relationships.
  • GCNs are Effective in Hypercomplex Domains: The successful integration of GCNs with hypercomplex algebras demonstrates that graph-based learning architectures can be effectively extended to these richer mathematical structures.
  • Simplicity Can Be Powerful: The decision to omit transformation matrices and activation functions in the HGC layers, while counter-intuitive to some GCN designs, proved effective for CDRec.
  • CDRec is Generalizable: The framework can recover simpler models like LightGCN (by using real numbers) and CCF/QCF (by setting layer depth to zero and using specific algebras), highlighting its flexibility.

Key Results

CDRec consistently outperformed state-of-the-art baselines across all three datasets for both click-through rate (CTR) prediction and top-K recommendation tasks.

  • CTR Prediction: CDRec achieved superior AUC and Accuracy scores. For instance, CDRec(S) showed relative improvements of 5.10%, 3.30%, and 12.63% in Precision@20 over the best baseline on the book, movie, and music datasets, respectively.
  • Top-K Recommendation: CDRec also demonstrated strong performance in Precision@K and Recall@K.
  • Hyper-parameter Sensitivity: The paper found that CDRec performs best with 1 or 2 layers (L), and that higher-dimensional algebras (like Sedenions and Trigintaduonions) often achieve better results, especially with fewer layers. The trade-off factor (w) between linear and interaction aggregators is also crucial, with optimal values varying across datasets.

Limitations and Future Work

  • Limitations:
    • The paper notes that while increasing hypercomplex algebra dimension initially boosts performance, it can eventually lead to a drop. This is attributed to a trade-off between algebra dimension and component embedding size (e) when the overall model size is fixed.
  • The optimal trade-off factor (w) varies across datasets, suggesting that careful tuning is required for different scenarios.
  • Future Work:
    • Integrate Side Information: Incorporate social networks and knowledge graphs into CDRec to further enhance performance.
  • Generate Explanations: Develop methods to provide explanations for recommendations, aiding user comprehension of behaviors and item attributes.
  • Explore Other Hypercomplex Systems: Investigate advanced hypercomplex systems like split-type and dual-type algebras for recommendation tasks.

Summary updated

Abstract

In this paper, we propose a recommendation framework named Cayley-Dickson Recommender. We introduce Cayley-Dickson construction which uses a recursive process to define hypercomplex algebras and their mathematical operations. We also design a graph convolution operator to learn representations in the hypercomplex space. To the best of our knowledge, it is the first time that Cayley-Dickson construction and graph convolution techniques have been used in hypercomplex recommendation. Compared with the state-of-the-art recommendation methods, our method achieves superior performance on real-world datasets.
BibTeX
@misc{li2021cdrec,
  author = {Anchen Li and Bo Yang and Huan Huo and Farookh Khadeer Hussain},
  title = {{CDRec: Cayley-Dickson Recommender}},
  year = {2021},
  eprint = {2112.08632},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2112.08632},
}
Figure