Link-Based Similarity Measures Using Reachability Vectors

Seok-Ho Yoon, Ji-Soo Kim, Jiwoon Ha, Sang‐Wook Kim, Minsoo Ryu, Ho‐Jin ChoiThe Scientific World JOURNAL 2014 · DOI

TL;DR

This paper introduces a novel link-based similarity measure that overcomes limitations of existing methods by representing objects as vectors based on reachability probabilities derived from "Random Walk with Restart." This approach achieves significantly higher accuracy in comparing scientific papers and web documents compared to established techniques.

What Problem Does This Paper Address?

Accurately measuring similarity between objects is crucial for many applications, from recommending products to organizing information. Existing link-based similarity measures, like SimRank, often rely on "pair-wise" or "level-wise" computation models. The authors argue that these models have inherent flaws: the pair-wise model can produce biased results where objects with more links appear less similar, while the level-wise model fails to consider all relevant indirect connections. This leads to counter-intuitive similarity scores, especially in domains with dense link structures like scientific literature or the web.

Methods

The core of the proposed approach is to represent each object as a vector where each dimension corresponds to another object in the dataset. The value in each dimension represents the "weight" of that object in characterizing the target object. This weight is determined by the probability of reaching the object from the target object, calculated using the "Random Walk with Restart" (RWR) strategy. The similarity between two objects is then computed using the standard cosine similarity between their respective vectors.

Two methods are proposed for generating these vectors:

  • WeightedSum Method: This method separately computes reachability using "inlinks" and "outlinks" and then combines them as a weighted sum. This allows for flexibility in assigning importance to incoming vs. outgoing links.
  • Undirected Method: This method treats all links as undirected, ignoring their original direction, and then computes reachability. This approach is simpler and aims to capture overall connectivity.

Datasets

The paper evaluates the proposed methods on two distinct datasets:

  • Scientific Papers: A dataset comprising 44,800 papers and 126,281 references, sourced from DBLP and Microsoft Academic Search (Libra).
  • Web Documents: A dataset of 1,227,038 web pages with 11,164,829 hyperlinks, taken from the TREC 2002 data.

The authors constructed answer sets for evaluation by grouping papers from specific sections of data mining textbooks (for scientific papers) and using keyword-related document sets from TREC 2002 (for web documents), assuming papers/documents within these groups are similar.

Key Insights and Ideas

  • Reachability as a Similarity Metric: The paper effectively reframes similarity not just by direct connections but by the probability of reaching one object from another, capturing a more nuanced sense of "closeness."
  • Overcoming Pair-wise/Level-wise Limitations: By using vector representations and cosine similarity, the proposed methods avoid the pitfalls of the pair-wise model's bias and the level-wise model's incompleteness.
  • Intuitive Similarity Scores: The new approach produces similarity scores that align better with human intuition, especially in cases where existing methods yielded zero similarity for indirectly related objects.
  • Flexibility in Link Handling: The distinction between the WeightedSum and Undirected methods highlights the trade-off between explicitly modeling link directionality and simplifying the problem for potentially better overall performance.

Key Results

  • Improved Accuracy: Both proposed methods, WeightedSum and Undirected, significantly outperform existing link-based measures (SimRank, rvs-SimRank, P-Rank) on both scientific papers and web documents.
  • Undirected Method Dominance: The Undirected method consistently showed the best performance, achieving higher accuracy improvements than the WeightedSum method.
  • Specific Improvements: On scientific papers, the Undirected method improved accuracy by 16% on average and up to 20% compared to SimRank. For web documents, it achieved a 34% average improvement and up to 43% compared to SimRank.
  • Qualitative Validation: The methods produced similarity results that were more aligned with intuition, particularly in cases where existing methods failed to recognize indirect relationships. For example, in Figure 2, objects with more links were correctly identified as similar to their counterparts with fewer links.

Limitations and Future Work

  • Subjectivity of Similarity: The authors acknowledge that determining the "correct" similarity for indirectly related objects (as in Figure 3) is subjective, making it difficult to definitively prove the absolute correctness of their results, though they argue for greater intuitiveness.
  • Parameter Tuning: The WeightedSum method requires careful tuning of weights for inlinks and outlinks, which is domain-dependent and determined through experimentation.
  • Computational Complexity: While the proposed methods are claimed to be more efficient than some existing ones in terms of computation, the complexity analysis shows an overall time complexity of O(n³) for similarity calculation, which can be significant for very large datasets. The paper mentions potential optimizations using off-line computation of inverse matrices and low-rank approximation for efficiency.
  • Future Work: The paper suggests exploring further optimizations for computational efficiency, particularly for large-scale applications, and potentially applying the methods to other domains with link structures.

Summary updated

Abstract

We present a novel approach for computing link-based similarities among objects accurately by utilizing the link information pertaining to the objects involved. We discuss the problems with previous link-based similarity measures and propose a novel approach for computing link based similarities that does not suffer from these problems. In the proposed approach each target object is represented by a vector. Each element of the vector corresponds to all the objects in the given data, and the value of each element denotes the weight for the corresponding object. As for this weight value, we propose to utilize the probability of reaching from the target object to the specific object, computed using the "Random Walk with Restart" strategy. Then, we define the similarity between two objects as the cosine similarity of the two vectors. In this paper, we provide examples to show that our approach does not suffer from the aforementioned problems. We also evaluate the performance of the proposed methods in comparison with existing link-based measures, qualitatively and quantitatively, with respect to two kinds of data sets, scientific papers and Web documents. Our experimental results indicate that the proposed methods significantly outperform the existing measures.
BibTeX
@article{yoon2014link,
  author = {Seok-Ho Yoon and Ji-Soo Kim and Jiwoon Ha and Sang‐Wook Kim and Minsoo Ryu and Ho‐Jin Choi},
  title = {{Link-Based Similarity Measures Using Reachability Vectors}},
  journal = {The Scientific World JOURNAL},
  year = {2014},
  doi = {10.1155/2014/741608},
}

Loading related content...

Figure