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:
- Factorization-based Approaches: Graph Factorization (GF), Laplacian Eigenmaps (LE), Locally Linear Embedding (LLE), HOPE, and GraRep.
- Random Walk-based Approaches: DeepWalk, Node2vec, and Role2vec.
- Deep Learning-based Approaches: DNGR, SDNE, and GraphSAGE.
- 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.
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.
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