Efficiently Discovering Hammock Paths from Induced Similarity Networks

Mahmud Shahriar Hossain, Michael Narayan, Naren RamakrishnanarXiv 2010 · arXiv

Abstract

Similarity networks are essential for discovery in large-scale datasets, yet materializing these networks for path-finding is often computationally prohibitive. This paper presents an algorithmic framework for identifying "hammock paths"—chains of highly similar entities—without full network materialization. By integrating concept lattices with A* search and admissible heuristics like the Soergel distance, the proposed method efficiently connects disparate items across massive bipartite datasets, such as linking unrelated films or mapping clinical trial comorbidities.

Introduction

Modern recommendation and discovery systems frequently operate on unipartite similarity networks induced from bipartite data. For instance, a movie-movie network can be derived from a movie-user rating matrix, where two films are connected if they share a sufficient number of common raters. However, as datasets scale to millions of entities (e.g., Netflix, PubMed), the number of potential edges grows quadratically, making it impossible to pre-calculate and store the entire graph in memory.

The core challenge is finding paths between distant nodes "on-the-fly." Standard algorithms like Dijkstra’s or Breadth-First Search (BFS) typically require a materialized graph. This paper addresses this by exploring only the most promising local neighborhoods, enabling the discovery of "hammock paths" through massive datasets without the overhead of full materialization.

Methodology

Hammock Paths and Cliques

The authors define a "hammock" of width $w$ as a pair of objects sharing at least $w$ features. A sequence of such pairs forms a hammock path. To enhance the robustness of these connections, the framework incorporates cliques—groups of $k$ objects where every pair satisfies the hammock requirement. As shown in Figure 1, increasing the clique size creates denser, more reliable paths between distant entities like Roman Holiday and Terminator 3.

Visualizing hammock paths and cliques of varying sizes.

To avoid scanning the entire database for every query, the authors utilize concept lattices (specifically the CHARM-L algorithm). This structure organizes data into "redescription sets"—groups of objects sharing identical features. This allows the search algorithm to quickly identify potential neighbors in the similarity network without a full scan.

A concept lattice structure derived from a movie-user rating matrix.

The navigation through this lattice is guided by A* search. To ensure efficiency and optimality, the authors employ the Soergel distance as an admissible heuristic. Because the Soergel distance satisfies the triangle inequality, it provides a lower bound on the distance to the target, preventing the search from overestimating and ensuring the shortest path is found.

Successor Generation

The framework evaluates three strategies for identifying the next "hop" in a path: Cover Trees, Nearest Neighbors Approximation (NNA), and $k$-Clique Near Neighbor ($k$CNN). The $k$CNN method proved superior by directly incorporating the clique size constraints into the search process.

Experimental Evaluation

The approach was tested on four datasets: a synthetic movie subset, the full Netflix dataset (17k movies, 480k users), PubMed abstracts (161k publications), and ClinicalTrials.gov data (66k trials).

Key Results

  • Computational Efficiency: On the PubMed dataset, the Soergel distance heuristic reduced node exploration by over 300% and runtime by 800% compared to standard BFS.
  • Path Discovery: The $k$CNN strategy successfully identified paths of length 13-14 in under 120 seconds, outperforming Cover Tree and NNA methods which often timed out on long-range queries.
  • Qualitative Insights: In clinical data, the algorithm mapped a logical path from congestive heart failure to kidney transplantation, traversing intermediate nodes like atrial fibrillation and cardiac ablation. This demonstrates the algorithm's ability to capture real-world research overlaps and medical co-morbidities.

Discussion and Conclusion

The study reveals a fundamental trade-off: increasing hammock width (shared features) makes links harder to find but more specific, while increasing clique size (group similarity) leads to shorter, denser paths. While the current implementation uses a branching factor limit to maintain speed—which may sacrifice completeness—it offers a scalable solution for real-time discovery.

Future work includes developing more compressed data representations and exploring alternative distance measures to accommodate diverse data distributions. By avoiding full network materialization, this framework provides a powerful tool for navigating the "hidden" connections in massive, complex datasets.

Summary updated

BibTeX
@misc{hossain2010efficiently,
  author = {Mahmud Shahriar Hossain and Michael Narayan and Naren Ramakrishnan},
  title = {{Efficiently Discovering Hammock Paths from Induced Similarity Networks}},
  year = {2010},
  eprint = {1002.3195},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1002.3195},
}
Figure