The topological face of recommendation: models and application to bias detection

Erwan Le Merrer, Gilles Trédan

Abstract

Recommendation plays a key role in e-commerce and in the entertainment industry. We propose to consider successive recommendations to users under the form of graphs of recommendations. We give models for this representation. Motivated by the growing interest for algorithmic transparency, we then propose a first application for those graphs, that is the potential detection of introduced recommendation bias by the service provider. This application relies on the analysis of the topology of the extracted graph for a given user; we propose a notion of recommendation coherence with regards to the topological proximity of recommended items (under the measure of items' k-closest neighbors, reminding the "small-world" model by Watts & Stroggatz). We finally illustrate this approach on a model and on Youtube crawls, targeting the prediction of "Recommended for you" links (i.e., biased or not by Youtube).

Introduction

Modern recommender systems, particularly on platforms like YouTube, often operate as "black boxes." While standard performance metrics like precision and recall evaluate accuracy, they fail to provide transparency regarding the underlying logic or potential biases introduced by the service provider. This paper introduces a novel auditing framework that represents recommendation outputs as directed graphs. By analyzing the topological structure of these "recommendation graphs," we can detect "introduced bias"—edges created for economic or legal reasons rather than pure item similarity—using principles from small-world network theory.

Methodology

Graph Construction

We model recommendations as a user-graph, where nodes represent items (e.g., videos) and directed edges represent recommendation links. These graphs are constructed by recursively following recommendations from a seed item up to a specific depth ($h$).

Small-World Analysis and Bias Detection

Our core hypothesis is that "natural" recommendations (based on similarity) connect topologically close items, whereas "biased" recommendations act as long-range shortcuts. Similar to the Watts-Strogatz model, these shortcuts significantly reduce the average path length of the graph. To identify these edges, we employ edge-betweenness centrality, a metric that highlights "bridge" edges connecting disparate clusters. Edges with high betweenness are flagged as potentially biased shortcuts.

Experimental Setup

The framework was validated using two datasets:

  1. YouTube Crawls: Recommendations were tracked starting from a popular video, comparing a "new user" (no history) against a "returning user" (with cookies). YouTube's "Recommended for you" tags served as a ground-truth proxy for biased/personalized edges.
  2. Synthetic Model: A controlled k-Nearest Neighbors (kNN) model in a $d$-dimensional vector space allowed for the injection of known bias (edges to distant items) to test detection sensitivity.

Results and Discussion

Topological Signatures of Personalization

Analysis reveals that user history significantly alters the recommendation space. As seen in Figure 1, the graph for a returning user is markedly denser and exhibits fewer distinct clusters compared to that of a new user. This suggests that personalization algorithms tend to "lock" users into a more redundant and constrained set of content.

4-hops recommendation graphs from a Youtube video: new user (left) and returning user (right).

Path Length Compression

The introduction of biased edges fundamentally shifts the graph's geometry. Figure 2 demonstrates that the presence of "Recommended for you" links (biased edges) shifts the distribution of path lengths toward lower values, confirming the shortcut hypothesis.

Distribution of graph path lengths for the synthetic model (left) and YouTube crawl (right).

Detection Performance

Using edge-betweenness, we successfully distinguished biased edges from standard ones. In the YouTube experiment, our algorithm identified nearly 50% of the biased set by inspecting only the top 12.5% of edges ranked by betweenness. ROC analysis further confirmed that this graph-based heuristic significantly outperforms random detection across both synthetic and real-world scenarios.

Conclusion

By treating recommendation outputs as a "topological face," we can audit black-box systems without internal access. Our results show that biased recommendations leave detectable footprints in the form of graph shortcuts. Future work will explore the scalability of these metrics and their application to deep-learning-based recommenders.

Summary updated

Abstract

Recommendation plays a key role in e-commerce and in the entertainment industry. We propose to consider successive recommendations to users under the form of graphs of recommendations. We give models for this representation. Motivated by the growing interest for algorithmic transparency, we then propose a first application for those graphs, that is the potential detection of introduced recommendation bias by the service provider. This application relies on the analysis of the topology of the extracted graph for a given user; we propose a notion of recommendation coherence with regards to the topological proximity of recommended items (under the measure of items' k-closest neighbors, reminding the "small-world" model by Watts & Stroggatz). We finally illustrate this approach on a model and on Youtube crawls, targeting the prediction of "Recommended for you" links (i.e., biased or not by Youtube).
BibTeX
@inproceedings{merrer2017topological,
  author = {Erwan Le Merrer and Gilles Trédan},
  title = {{The topological face of recommendation: models and application to bias detection}},
  booktitle = {COMPLEX NETWORKS},
  year = {2017},
  url = {https://openreview.net/forum?id=VLbavb92yaI},
}
Figure