Recently, several papers proposed different approaches to construct conceptual hierarchies from tags collated from social Web sites. Mika [3] uses a graphbased approach to construct a network of related tags, projected from either a user-tag or object-tag association graphs. Although there is no evaluation of the induced broader/narrower relations, the work provides a good suggestion to infer them by using betweenness centrality and set theory. Other works apply clustering techniques to keywords expressed in tags, and use their co-occurrence statistics to produce conceptual hierarchies [10, 5]. In a variation of the clustering approach, Heymann [11] uses graph centrality in the similarity graph of tags. In particular, the tag with the highest centrality would be more abstract than that with a lower centrality; thus it should be merged to the hierarchy before the latter, to guarantee that more general node gets closer to the root node. Schmitz [4]
has applied a statistical subsumption model [12] to induce hierarchical relations of tags.

We believe that the previously mentioned works suffer from the "popularitygenerality" problem that arises when using tags to induce a hierarchy. Specifically, a certain tag may be used more frequently not only because it is more general, but because it is more popular with users. In Flickr, for example, there are more photos tagged with car (1, 325, 512) than with vehicle (71, 498). If we apply clustering approaches, car will be more general than vehicle since, the former is likely to have higher centrality than the latter. And if we apply statistical subsumption model, the former would be likely to subsume the latter since there is a higher chance that photos tagged with vehicle are also tagged with car. Of course, we believe that tag statistics are a good source of evidence for inducing hierarchies; however, tag statistics alone may not be adequate to distinguish between tag popularity and generality.

There is another line of research that focuses on exploiting partial hierarchies contributed by users. *GiveALink* project [13] collects bookmarks donated by users. Each bookmark is organized in a tree structure as folder and sub folders by an individual user. Based on tree structures, similarities between URLs are computed and used for URL recommendation and ranking. Although this project does not concentrate on conceptual hierarchy construction, it provides a good motivation to exploit explicit partial structures like folder and subfolder relations. Our approach is in the same spirit as *GiveALink* - we exploit collection and set relations contributed by users on a social Web site to construct conceptual hierarchies. We hypothesize that generality-popularity problem of keywords in collection-set relation space is less than that in tag space. Although people may use a keyword "Washington" far more than "United States" to name their collections and sets, not so many people would put their "United States" album into "Washington" super album, however.

Our approach is similar in spirit to ontology alignment, *e.g.*, [14]. However, unlike those works, which merge a small number of deep and detailed hierarchies, we merge large number of noisy, shallow hierarchies.