Empirical Comparison of Graph Embeddings for Trust-Based Collaborative Filtering

Tomislav Duricic, Hussain Hussain, Emanuel Lacic, Dominik Kowald, Denis Helic, Elisabeth LexarXiv 2020 · DOI · arXiv

TL;DR

This paper presents a comprehensive empirical comparison of 12 graph embedding techniques across four algorithmic families for trust-based collaborative filtering. Focusing on the notorious cold-start problem, the authors reveal that random-walk-based methods (like Node2vec and DeepWalk) consistently outperform factorization and deep learning approaches in accuracy, novelty, and diversity, while graph embeddings as a whole dramatically improve user coverage.

What Problem Does This Paper Address?

Collaborative filtering (CF) recommender systems heavily rely on historical user ratings to find similarities between users. Consequently, they suffer from the "cold-start" problem: when a user is new or has rated very few items, the system cannot reliably find similar neighbors to generate recommendations.

Trust-based recommender systems attempt to solve this by leveraging social trust networks (where nodes are users and edges represent explicit or implicit trust relationships). However, these trust networks are typically highly sparse, making it difficult to locate $k$-similar neighbors using traditional graph metrics. While graph embedding methods can map users into a dense, low-dimensional latent space to uncover hidden structural similarities, there has been a lack of systematic evaluation comparing different embedding families across both accuracy and "beyond-accuracy" metrics (novelty, diversity, and user coverage) for cold-start users.

Methods

The authors benchmark 12 state-of-the-art graph embedding methods, dividing them into four distinct families:

  1. Factorization-based Approaches: Graph Factorization (GF), Laplacian Eigenmaps (LE), Locally Linear Embedding (LLE), HOPE, and GraRep.
  2. Random Walk-based Approaches: DeepWalk, Node2vec, and Role2vec.
  3. Deep Learning-based Approaches: DNGR, SDNE, and GraphSAGE.
  4. LINE: Large-scale Information Network Embedding (which preserves 1st- and 2nd-order proximities separately).

Crucially, the authors convert the directed trust networks into undirected graphs, which empirically reduces sparsity and improves recommendation accuracy across almost all methods. Once user embeddings are generated, recommendations are served using a $k$-nearest neighbor ($k$-NN, where $k=40$) approach based on pairwise cosine similarity. These embedding methods are evaluated against five traditional trust-based baselines (e.g., Jaccard similarity, Katz similarity, and direct trust propagation).

Datasets

The evaluation is conducted on three publicly available trust-based recommendation datasets: Epinions, Ciao, and Filmtrust.

To simulate a strict cold-start setting, the authors split the data based on rating counts:

  • Warm-start users (>10 ratings) form the validation set used for hyperparameter optimization.
  • Cold-start users ($\le 10$ ratings) form the test set used to measure final algorithmic performance.
Table 1. Dataset statistics.
Table 2. Number of users per dataset split.

Key Insights and Ideas

  • Symmetry Beats Directionality: Counter-intuitively, stripping away the direction of trust edges and treating the network as undirected yields better recommendation accuracy. This happens because making the graph symmetric artificially increases the average node degree, mitigating the extreme sparsity of trust graphs.
  • Random Walks Rule the Graph: Random-walk-based methods (DeepWalk and Node2vec) are highly robust. By capturing both local neighborhoods and broader network macro-structures through flexible walks, they create superior latent representations compared to rigid matrix factorizations or complex deep learning architectures.
  • The Novelty-Accuracy Synergy: The authors discovered a statistically significant positive correlation between recommendation accuracy (nDCG) and novelty. In trust-based ecosystems, users actually prefer discovering long-tail, novel items over predictable, popular ones.
  • Coverage Unlocked: Traditional trust propagation methods fail to give recommendations to users who don't have direct or close trust links. Graph embeddings project all reachable nodes into the same continuous space, drastically expanding the system's ability to serve cold-start users.

Key Results

  • Top Performers: Node2vec and DeepWalk secured the 1st and 2nd overall ranks in accuracy (nDCG) across all datasets. DeepWalk demonstrated statistically significant superiority in both nDCG and novelty on Epinions and Ciao.
  • Beyond-Accuracy Success: Node2vec and DeepWalk didn't just win on accuracy; they also scored exceptionally high on novelty and diversity, proving that you don't always have to sacrifice one for the other.
  • Massive Coverage Gains: Graph embeddings achieved fixed, maximum possible user coverage based on graph connectivity (e.g., 100% on Epinions, 13.1% on Ciao, and 44.2% on Filmtrust), vastly outperforming direct trust baselines like Trust_dir, which only managed a dismal 3.9% coverage on Ciao.
Table 3: Comprehensive performance breakdown of baseline vs. embedding methods across all three datasets.

Limitations and Future Work

  • Loss of Asymmetry: Converting directed graphs to undirected ones discards the inherent asymmetry of trust (i.e., User A trusts User B, but User B might not trust User A). Future work will focus on embedding methods that preserve edge directionality.
  • Under-optimized Deep Learning: Complex deep models like SDNE underperformed, potentially due to an insufficiently wide hyperparameter search space.
  • Missing Item/User Features: The current embeddings only leverage the topology of the trust network. The authors plan to integrate user and item features from the rating matrix directly into the graph embedding process to create a more holistic hybrid recommender system.

Summary updated

Abstract

In this work, we study the utility of graph embeddings to generate latent user representations for trust-based collaborative filtering. In a cold-start setting, on three publicly available datasets, we evaluate approaches from four method families: (i) factorization-based, (ii) random walk-based, (iii) deep learning-based, and (iv) the Large-scale Information Network Embedding (LINE) approach. We find that across the four families, random-walk-based approaches consistently achieve the best accuracy. Besides, they result in highly novel and diverse recommendations. Furthermore, our results show that the use of graph embeddings in trust-based collaborative filtering significantly improves user coverage.
BibTeX
@misc{duricic2020empirical,
  author = {Tomislav Duricic and Hussain Hussain and Emanuel Lacic and Dominik Kowald and Denis Helic and Elisabeth Lex},
  title = {{Empirical Comparison of Graph Embeddings for Trust-Based Collaborative Filtering}},
  year = {2020},
  eprint = {2003.13345},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2003.13345},
}
Figure