# Growing A Tree In The Forest: Constructing Folksonomies By Integrating Structured Metadata

Anon Plangprasopchok USC Information Sciences Institute Marina del Rey, CA, USA
plangpra@isi.edu Kristina Lerman USC Information Sciences Institute Marina del Rey, CA, USA
lerman@isi.edu Lise Getoor Department of Computer Science University of Maryland College Park, MD, USA
getoor@cs.umd.edu

## Abstract

Many social Web sites allow users to annotate the content with descriptive metadata, such as tags, and more recently to organize content hierarchically. These types of structured metadata provide valuable evidence for learning how a community organizes knowledge. For instance, we can aggregate many personal hierarchies into a common taxonomy, also known as a folksonomy, that will aid users in visualizing and browsing social content, and also to help them in organizing their own content. However, learning from social metadata presents several challenges, since it is sparse, shallow, ambiguous, noisy, and inconsistent. We describe an approach to folksonomy learning based on relational clustering, which exploits structured metadata contained in personal hierarchies. Our approach clusters similar hierarchies using their structure and tag statistics, then incrementally weaves them into a deeper, bushier tree. We study folksonomy learning using social metadata extracted from the photosharing site Flickr, and demonstrate that the proposed approach addresses the challenges. Moreover, comparing to previous work, the approach produces larger, more accurate folksonomies, and in addition, scales better.

## Categories And Subject Descriptors

H.2.8 [DATABASE MANAGEMENT**]: Database Applications—**Data mining; I.2.6 [ARTIFICIAL INTELLIGENCE**]: Learning—**Knowledge Acquisition

## General Terms

Algorithms, Experimentation, Human Factors, Measurement

## Keywords

Folksonomies, Taxonomies, Collective Knowledge, Social Information Processing, Data Mining, Social Metadata, Relational Clustering Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. To copy otherwise, to republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. KDD'10, July 25–28, 2010, Washington, DC, USA. Copyright 2010 ACM 978-1-4503-0055-1/10/07 ...$10.00.

## 1. Introduction

The social Web has changed the way people create and use information. Sites like Flickr, Del.icio.us, YouTube, and others, allow users to publish and organize content by annotating it with descriptive keywords, or tags. Some web sites also enable users to organize content hierarchically. The photo-sharing site Flickr, for example, allows users to group related photos in sets, and related sets in collections. Although these types of social metadata lack formal structure, they capture the collective knowledge of Social Web users.

Once mined from the traces left by many users, such collective knowledge will add a rich semantic layer to the content of the Social Web that will potentially support many tasks in information discovery such as personalization, data mining, and information management.

A community's knowledge can be expressed through a common taxonomy, also called a folksonomy**, that is learned**
from social metadata created by many users. Compared to existing hierarchies, such as Linnaean classification system or WordNet, automatically learned folksonomies are attractive because they (1) represent collective agreement of many individuals; (2) are relatively inexpensive to obtain; (3) can adapt to evolving vocabularies and community's information needs; and (4) they are directly tied to the annotated content. A folksonomy can facilitate browsing of user-generated content, and help users visualize how their own content fits within the community's or aid them in organizing it.

Learning a folksonomy by integrating structured metadata created by many users presents a number of challenges.

Since users are free to annotate data according to their own preferences, social metadata is noisy, shallow, sparse, ambiguous, conflicting, multi-faceted**, and expressed at** inconsistent granularity levels **across many users. Several recent**
works have addressed some of the above challenges. For instance, [7, 15] proposed inducing folksonomies from tags by utilizing tag statistics. The basic motivation behind these approaches is that more frequent tags describe more general concepts. However, frequency-based methods cannot distinguish between more general and more popular concepts. In our previous work, sig **[12], we overcame this problem by**
using user-specified relations, extracted from personal hierarchies. Nevertheless, it ignored other evidence, e.g., structure of hierarchies and tags, which potentially address the challenges listed above.

We propose a novel approach to learn folksonomies from social metadata in the form of tags and user-specified shallow hierarchies. Our approach is driven by a similarity mea-