folksonomies are deep. Last, sap **demonstrates many advantages as presented in Section 5.**
The sapling merging approach described in this paper is an extension of collective relational clustering approach **used**
for entity resolution [1]. That work proposed a method to identify and disambiguate entities, such as authors, that utilizes two types of evidence: intrisic and extrinsic features.

Intrinsic features are associated with specific instances, **such**
as author names, while extrinsic features are derived from structural evidence, e.g., co-authors in a citations database. Intuitively, two names refer to the same author if they are similar and their co-author names refer to the same set of authors. Analogously, we identify and disambiguate concept names from names and tags (intrinsic) and neighboring nodes' features (extrinsic). However, for efficiency reasons, we use the naive version of the relational clustering, where we directly use the features from neighbors as the extrinsic features, rather than cluster labels.

Handling mutual shortcuts by keeping the sapling which is more similar to the ancestor is similar in spirit to the minimum evolution assumption in [19]. Specifically, a certain hierarchy should not have any sudden changes from a parent to its child concepts. Our approach is also similar to several works on ontology alignment (e.g. [4, 17]). However, unlike those works, which merge a small number of deep, detailed and consistent concepts, we merge large number of noisy and shallow concepts, which are specified by different users.

## 7. Conclusion

This paper describes an approach which incrementally combines a large number of shallow hierarchies specified by different users into common, denser and deeper folksonomies. The approach addresses the challenges of learning folksonomies from social metadata and demonstrates several advantages over the previous work. Additionally, it is general enough for other domains, such as tags/bundles in Delicious **and files/folders in personal workspaces.**
For the future work, in addition to automatically separating broader/narrower from related-to relations, we would like to develop a systematic way to handle individual saplings whose child nodes are from different facets. This will improve the quality of the learned folksonomies by not mixing concepts from different facets. We are also working on combining more sources of evidence such as geographical information for learning accurate folksonomies. Lastly, we would like to frame the approach in a fully probabilistic way
(e.g., [18, 2]), which provides a systematic way to combine heterogeneous evidence, and takes into account uncertainties on similarities between concepts and relations.

## Acknowledgements

This material is based upon work supported by the National Science Foundation under Grant No. IIS-0812677.

## 8. References

[1] I. Bhattacharya and L. Getoor. Collective entity resolution in relational data. ACM Trans. Knowl.

Discov. Data**, 1(1):5, 2007.**
[2] M. Broecheler and L. Getoor. Probabilistic similarity logic. In Proceedings of International Workshop on Statistical Relational Learning**, 2009.**
[3] C. H. Brooks and N. Montanez. Improved annotation of the blogosphere via autotagging and hierarchical clustering. In Proceedings of the World Wide Web conference**, 2006.**
[4] J. Euzenat and P. Shvaiko. Ontology Matching.

Springer-Verlag, 2007.

[5] S. A. Golder and B. A. Huberman. Usage patterns of collaborative tagging systems. J. Inf. Sci.,
32(2):198–208, April 2006.

[6] M. A. Hearst. Automatic acquisition of hyponyms from large text corpora. In Proceedings of the Annual Meeting of the Association for Computational Linguistics**, 1992.**
[7] P. Heymann and H. Garcia-Molina. Collaborative creation of communal hierarchical taxonomies in social tagging systems. Technical Report 2006-10, Stanford University, Stanford, CA, USA, April 2006.

[8] A. Maedche and S. Staab. Measuring similarity between ontologies. In Proceedings of the Knowledge Engineering and Knowledge Management**, 2002.**
[9] A. Mathes. Folksonomies: cooperative classification and communication through shared metadata. 2004.

[10] P. Mika. Ontologies are us: A unified model of social networks and semantics. J. Web Sem.**, 5(1):5–15, 2007.**
[11] A. E. Monge and C. Elkan. An efficient domain-independent algorithm for detecting approximately duplicate database records. In Proceedings of the SIGMOD workshop on Data Mining and Knowledge Discovery**, 1997.**
[12] A. Plangprasopchok and K. Lerman. Constructing folksonomies from user-specified relations on flickr. In Proceedings of the World Wide Web conference**, 2009.**
[13] T. Rattenbury, N. Good, and M. Naaman. Towards automatic extraction of event and place semantics from flickr tags. In Proceedings of the conference on Research and development in information retrieval, 2007.

[14] M. Sanderson and W. B. Croft. Deriving concept hierarchies from text. In Proceedings of the conference on Research and development in information retrieval, pages 206–213, 1999.

[15] P. Schmitz. Inducing ontology from flickr tags. In Proceedings of the WWW workshop on Collaborative Web Tagging Workshop**, 2006.**
[16] R. Snow, D. Jurafsky, and A. Y. Ng. Semantic taxonomy induction from heterogenous evidence. In Proceedings of the Annual Meeting of the Association for Computational Linguistics**, 2006.**
[17] O. Udrea, L. Getoor, and R. J. Miller. Leveraging data and structure in ontology integration. In SIGMOD Conference**, 2007.**
[18] J. Wang and P. Domingos. Hybrid markov logic networks. In Proceedings of Association for the Advancement of Artificial Intelligence**, 2008.**
[19] H. Yang and J. Callan. A metric-based framework for automatic taxonomy induction. In Proceedings of the Annual Meeting of the Association for Computational Linguistics, 2009.