The Topological Face of Recommendation

Erwan Le Merrer, Gilles Trédan

TL;DR

This paper proposes representing recommendation systems' outputs as graphs to analyze their structure and detect potential biases. By crawling recommendation interfaces and modeling them as user-graphs, the authors demonstrate that topological analysis can reveal how a service "knows" a user and can even help identify biased recommendations, particularly those that deviate from expected item locality.

What Problem Does This Paper Address?

Recommender systems are ubiquitous, but their inner workings are often opaque, leading to concerns about algorithmic transparency and bias. While traditional evaluation metrics like precision and recall assess performance, they don't offer insights into how recommendations are made or if they are being manipulated. The authors argue that the output of recommenders, which is essentially a set of suggested items, can be viewed as a graph. This graph representation, they propose, can unlock new analytical capabilities, particularly for understanding user behavior and detecting biases introduced by the service provider. The challenge is to develop methods to extract and analyze these recommendation graphs, especially from an external user's perspective, and to leverage their topology to identify non-standard recommendation patterns that might indicate bias.

Methods

The core of the paper is the proposal to model recommendation outputs as graphs. They introduce two main graph representations:

  • Global Graph of Recommendations ($G_t$): This represents all recommendations made by a service at a given time $t$. It's primarily of interest to service providers for understanding overall recommendation patterns.
  • User-Graph of Recommendations ($G_t(u)$): This focuses on the recommendations made to a specific user $u$. This is the graph the authors primarily use for their analysis, as it can be observed by the user herself.

To construct these graphs, they employ a web-crawling approach. Starting from an initial item (e.g., a YouTube video), they recursively crawl recommended items up to a specified depth ($h$). This process builds a directed graph where nodes are items and edges represent recommendations.

For bias detection, they propose a model that considers two recommenders: an "official" one ($R$) and a potentially biased one ($R'$). They introduce a parameter ($i_{RR'}$) to control the degree of dependency between the features used by these recommenders. The hypothesis is that biased edges will deviate from the "normal" topological properties of recommendation graphs, such as item locality. They then use algorithms like edge-betweenness centrality to identify these potentially biased edges.

Datasets

The paper uses data from two main sources for their experiments:

  • Model Graph: A simulated recommendation graph generated based on their proposed biased recommendation model.
  • YouTube Crawls: Real-world data collected by crawling YouTube's recommendation interface. They specifically mention using crawls from a returning user for a particular video, with and without "Recommended for you" links (which they treat as ground truth for biased edges).

Key Insights and Ideas

  • Recommendation Outputs as Graphs: The fundamental idea that recommendation outputs can be effectively modeled as graphs opens up a rich area for analysis using established graph theory tools.
  • User-Graphs Reveal System Knowledge: Comparing user-graphs from "new" vs. "returning" users on YouTube revealed significant topological differences. The returning user's graph was more compact, suggesting the recommender system had learned more about the user and was providing more targeted recommendations.
  • Topology as a Bias Indicator: The paper posits that biased recommendations will likely manifest as "long-range links" in the recommendation graph, deviating from the expected "local" connections based on item similarity. This is analogous to the "small-world" network model.
  • Algorithmic Transparency via Topology: By analyzing the structure of recommendation graphs, users or researchers can gain insights into the recommender's behavior and potentially detect if certain recommendations are being pushed for reasons other than direct item relevance.

Key Results

  • Topological Differences: Crawls from new vs. returning users on YouTube showed distinct graph structures, with returning users exhibiting more clustered and less diverse recommendation paths.
  • Bias Detection Feasibility: Experiments using the edge-betweenness centrality algorithm on both model and YouTube data showed promising results in identifying biased edges. For YouTube, this algorithm could identify close to 50% of the biased edges with a relatively low false positive rate (around 12.5%).
  • Impact of Bias on Graph Structure: The presence of biased edges was shown to significantly alter graph properties, such as path length distribution, making the graph more "compact," similar to the effect of long-range links in small-world networks.

Limitations and Future Work

  • Definition of Bias: The paper acknowledges that defining "bias" formally can be challenging and relies on observable topological consequences.
  • Crawler Limitations: The observed user-graph is an approximation of the system's true state, as crawling is sequential and the system might update recommendations between requests. They assume a practical scenario where updates are infrequent.
  • Future Work: The authors suggest generalizing their models to other recommender types (e.g., neural networks) and exploring further applications of recommendation graphs beyond bias detection. They also mention the potential for using these graphs to understand other aspects of personalization transparency.

Summary updated

Abstract

The success of Google’s PageRank algorithm popularized graphs as a tool to model the web’s navigability. At that time, the web topology was resulting from human edition of hyper-links. Nowadays, that topology is mostly resulting from algorithms. In this paper, we propose to study the topology realized by a class of such algorithms: recommenders. By modeling the output of recommenders as graphs, we show that a vast array of topological observations become easily accessible, using a simple web-crawler. We give models and illustrations for those graph representations. We then propose a graph-based methodology for addressing an algorithmic transparency problem: recommendation bias detection. We illustrate this approach on YouTube crawls, targeting the prediction of “Recommended for you” links.
BibTeX
@inproceedings{merrer2017topological,
  author = {Erwan Le Merrer and Gilles Trédan},
  title = {{The Topological Face of Recommendation}},
  booktitle = {COMPLEX NETWORKS},
  year = {2017},
  url = {https://openreview.net/forum?id=VLbavb92yaI},
}
Figure