TL;DR
This paper evaluates three popular tag relatedness measures—co-occurrence, cosine similarity, and FolkRank—by grounding them semantically in WordNet. The authors discover that while cosine similarity excels at identifying synonyms and spelling variants, simple co-occurrence and FolkRank are heavily biased toward broader, hierarchical concepts (hypernyms).
What Problem Does This Paper Address?
Collaborative tagging systems (or folksonomies), like the social bookmarking site del.icio.us, generate massive amounts of user-driven metadata. While this data is a goldmine for knowledge extraction and automated ontology learning, researchers often select tag similarity metrics in an ad-hoc fashion.
The core challenge is that "relatedness" is a vague term. Does a statistical relationship between two tags mean they are synonyms, hierarchical parent-child concepts, or just loosely related topics? This paper addresses this gap by formally analyzing what kind of semantic relationships different statistical metrics actually capture.
Methods
The authors evaluate three distinct measures of tag relatedness directly computed from a folksonomy's network structure:
- Tag Co-occurrence (
freq): A simple count of how many times two tags appear together in the same user post. - Cosine Similarity (
cosine): Rather than looking at direct co-occurrence, this computes the cosine similarity between the entire co-occurrence distribution vectors of two tags. It leverages the distributional hypothesis—words used in similar contexts tend to have similar meanings. - FolkRank (
folkrank): A graph-based centrality algorithm that adapts PageRank to the tri-partite structure (users, tags, resources) of folksonomies.
To provide a semantic baseline, the authors map the tags to WordNet synsets (synonym sets). They then compute well-established semantic distance metrics (taxonomic shortest-path length and the Jiang-Conrath distance) and analyze the exact edge composition (e.g., hypernym/parent vs. hyponym/child links) of the paths connecting the tags in WordNet.
Datasets
- del.icio.us Dataset: A large-scale snapshot crawled in November 2006, consisting of 476,378 users, 12,660,470 resources, and over 101 million tag assignments. The authors restricted their analysis to the 10,000 most frequent tags to mitigate data sparseness.
- WordNet: Used as the ground-truth semantic lexicon. Roughly 61% of the top 10,000 del.icio.us tags successfully mapped to WordNet's noun and verb hierarchies.
Key Insights and Ideas
- Context vs. Co-occurrence: Cosine similarity surfaces tags that share a context, even if they rarely appear together. This makes it incredibly effective at finding synonyms, alternative spellings (e.g.,
web2.0andweb-2.0), and cross-lingual translations (e.g.,gamesand the Germanspiel). - The Popularity Bias of Hierarchies: Direct co-occurrence and FolkRank are strongly biased toward high-frequency, general terms. Because specific tags frequently co-occur with broad category tags (e.g.,
javawithprogramming), these metrics naturally discover hierarchical relationships rather than synonyms. - Multi-word Lexeme Discovery: FolkRank uniquely shines at identifying multi-word phrases that users split into separate tags. For instance, it is the only algorithm that successfully links
openandsourcebi-directionally within its top results.
Key Results
- Metric Overlap: Co-occurrence and FolkRank share a massive overlap in their top-10 related tags (averaging 6.7 out of 10 tags). Cosine similarity, however, shows very little overlap with the other two (around 1.1 to 1.7 tags).
- Vocabulary Breadth: As shown in Figure 1, the average frequency rank of tags related via cosine similarity scales with the rank of the original tag. In contrast, co-occurrence and FolkRank consistently pull from the most popular tags in the dataset, regardless of the target tag's popularity.
- WordNet Proximity: Cosine similarity yields tags that are significantly closer in WordNet space, with an average shortest path length of 6.3, compared to 7.4 for co-occurrence and 7.8 for FolkRank.
- Path Traversal Behavior: When looking at paths of length 2 in WordNet (Figure 2), 90% of the paths generated by cosine similarity consist of one "up" (hypernym) edge and one "down" (hyponym) edge—the exact definition of a sibling/synonym relationship. Conversely, roughly half of the length-2 paths for co-occurrence and FolkRank consist of two consecutive "up" edges, confirming their tendency to target broader, more general concepts.
Limitations and Future Work
The primary limitation stems from WordNet itself: it is a static, English-only database that struggles to keep up with the fluid, multilingual, and community-specific vocabulary of live folksonomies. Additionally, WordNet's hierarchical distance metrics only work cleanly for nouns and verbs, leaving out adjectives.
For future work, the authors plan to explore vector spaces spanned specifically by users or resources and integrate these targeted similarity measures directly into automated ontology learning frameworks.
Summary updated