Comparing Personalized Relevance Algorithms for Directed Graphs

Luca Cavalcanti, Cristian Consonni, Martin Brugnara, David Laniado, Alberto Montresor

Abstract

We present an interactive Web platform that, given a directed graph, allows identifying the most relevant nodes related to a given query node. Besides well-established algorithms such as PageRank and Personalized PageRank, the demo includes Cyclerank, a novel algorithm that addresses some of their limitations by leveraging cyclic paths to compute personalized relevance scores. Our demo design enables algorithm and dataset comparison for exploring and gaining insights into a dataset. We provide 50 pre-loaded datasets from Wikipedia, Twitter, and Amazon.

Introduction: The Centrality Bias Problem

In massive directed graphs—such as Wikipedia link networks or Twitter interaction graphs—identifying nodes relevant to a specific "query" node is a fundamental task. Standard tools like PageRank provide global importance scores, while Personalized PageRank (PPR) attempts to narrow the focus to a specific starting point. However, PPR often suffers from "centrality bias," where globally popular nodes (e.g., "United States" or "New York Times") dominate the results regardless of the query, drowning out specific, niche relationships.

System Architecture and Methods

The proposed platform is built on a microservices architecture designed for extensibility and scalability. It consists of a Web UI, an API gateway for task scheduling, and containerized computation nodes that execute the relevance algorithms.

System architecture of the interactive platform.

The core innovation of the platform is CycleRank. Unlike traditional methods that focus on one-way link paths, CycleRank identifies mutual relevance by analyzing cycles. If a path exists from node A to B and another path returns from B to A, a strong structural bond is inferred. The algorithm weights these cycles based on length, using an exponential damping factor ($\sigma = e^{-n}$) to prioritize direct relationships.

Datasets

The platform includes 50 pre-loaded datasets:

  • WikiLinkGraphs: Snapshots of Wikipedia link networks across 9 languages (2003–2018).
  • Amazon Co-purchase Network: Over 548,000 products linked by customer purchase patterns.
  • Twitter Interaction Networks: Focused on specific events like COP27 and International Women’s Day.
  • Custom Data: Support for user-uploaded edgelist or pajek files.

Qualitative Analysis and Key Insights

The utility of CycleRank is most evident when compared to standard PageRank and PPR. By focusing on cyclic paths, CycleRank effectively ignores "sink" nodes or global hubs that lack a reciprocal relationship with the query.

Comparison of relevance results for "Freddy Mercury" and "Pasta" queries.

As shown in the comparison table, for the query "Pasta," PPR suggests "Bolognese sauce" and "Italy." In contrast, CycleRank identifies "Italian cuisine" and specific varieties like "Spaghetti," providing a more topically focused neighborhood. Similarly, for "Freddy Mercury," PPR returns the globally central "United States," whereas CycleRank correctly identifies his Queen bandmates.

Furthermore, the platform enables cross-language analysis. For the query "Fake news," the German Wikipedia links strongly to "Barack Obama," while the English version highlights "CNN" and "Facebook," demonstrating how relevance is shaped by cultural context.

Limitations and Future Work

Currently, the platform does not allow users to upload custom algorithm code due to security constraints. Additionally, while the microservices architecture handles significant loads, extremely large graphs or high cycle lengths ($K$) present computational challenges. Future work will focus on expanding supported dataset formats and integrating emerging relevance algorithms.

Summary updated

Abstract

We present an interactive Web platform that, given a directed graph, allows identifying the most relevant nodes related to a given query node. Besides well-established algorithms such as PageRank and Personalized PageRank, the demo includes Cyclerank, a novel algorithm that addresses some of their limitations by leveraging cyclic paths to compute personalized relevance scores. Our demo design enables two use cases: (a) algorithm comparison, comparing the results obtained with different algorithms, and (b) dataset comparison, for exploring and gaining insights into a dataset and comparing it with others. We provide 50 pre-loaded datasets from Wikipedia, Twitter, and Amazon and seven algorithms. Users can upload new datasets, and new algorithms can be easily added. By showcasing efficient algorithms to compute relevance scores in directed graphs, our tool helps to uncover hidden relationships within the data, which makes of it a valuable addition to the repertoire of graph analysis algorithms.
BibTeX
@misc{cavalcanti2024comparing,
  author = {Luca Cavalcanti and Cristian Consonni and Martin Brugnara and David Laniado and Alberto Montresor},
  title = {{Comparing Personalized Relevance Algorithms for Directed Graphs}},
  year = {2024},
  eprint = {2405.02261},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2405.02261},
}
Figure