# Integrating Structured Metadata With Relational Affinity Propagation Anon Plangprasopchok And Kristina Lerman

USC Information Sciences Institute Marina del Rey, CA
Lise Getoor Department of Computer Science University of Maryland, College Park

## Abstract

Structured and semi-structured data describing entities, taxonomies and ontologies appears in many domains. There is a huge interest in integrating structured information from multiple sources; however integrating structured data to infer complex common structures is a difficult task because the integration must aggregate similar structures while avoiding structural inconsistencies that may appear when the data is combined. In this work, we study the integration of structured social metadata: shallow personal hierarchies specified by many individual users on the Social Web, and focus on inferring a collection of integrated, consistent taxonomies. We frame this task as an optimization problem with structural constraints. We propose a new inference algorithm, which we refer to as *Relational Affinity Propagation (RAP)* that extends affinity propagation (Frey and Dueck 2007) by introducing structural constraints. We validate the approach on a real-world social media dataset, collected from the photosharing website Flickr. Our empirical results show that our proposed approach is able to construct deeper and denser structures compared to an approach using only the standard affinity propagation algorithm.

## Introduction

Structured and semi-structured data describing entities, relationships among entities, and taxonomies and ontologies over them, appear in many domains. There is a great deal of interest in integrating structured information from multiple sources. Some of the areas that have seen much active research include bioinformatics, aggregation services for commercial products and services, and more traditional enterprise database integration. Integrating structured data to infer complex common structures is a difficult task because the integration must aggregate similar structures while avoiding structural inconsistencies that may appear when the data is combined.

This problem becomes even more challenging when one is attempting to integrate numerous, heterogeneous metadata fragments, generated by multiple users. This data is inherently noisy and inconsistent, and there is certainly no single, unified structure to be found. On the other hand, finding and extracting the best exemplar or a set of good example structures can be highly beneficial.

Copyright c 2018, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.

In folksonomy learning (Plangprasopchok and Lerman 2009), structured metadata in the form of hierarchies of concepts created by many users on the Social Web is combined into a global hierarchy of concepts, that reflects how a community organizes knowledge. Users who create personal hierarchies to organize their content may use idiosyncratic categorization schemes (Golder and Huberman 2006) and naming conventions. Simply combining nodes with similar names is likely to lead to ill-structured graphs containing loops and shortcuts (multiple paths from one node to another), rather than a taxonomy.

In this paper, we present a probabilistic approach for aggregating relational data into a desired structure. Specifically, our task is to integrate many shallow personal hierarchies, namely *saplings*, into a deeper, more complete taxonomy. Our learning method, relational affinity propagation, extends affinity propagation (Frey and Dueck 2007) by introduces structural constraints that encourages the integration process to combine saplings into trees rather than an arbitrary graph containing loops and shortcuts. We show that embedding the constraints into the hierarchy learning process results in a more accurate merging of saplings that leads to a more consistent tree. We demonstrate the utility of the proposed approach on real-world data extracted from the photosharing site Flickr. Specifically, we combine shallow personal hierarchies created by Flickr users into common deeper hierarchies of concepts.

The objective of the optimization is to combine these small shallow hierarchies into a small number of, deeper and denser hierarchies that represent how a community of users organizes their knowledge. This differs from classical taxonomy and ontology alignment settings (Euzenat and Shvaiko 2007) where there are typically just a few structures to align, and those structures are large with rich and deep structure and semantics; here we focus on the much messier setting, where we have many small fragments, created by end users with a variety of purposes in mind. In these settings, coming up with a single integrated taxonomy is infeasible, so instead we focus on constructing a small number of useful taxonomies.

We motivate our approach with an example of learning a common taxonomy of concepts from shallow personal hierarchies (saplings) created by many users and illustrate some of the challenges that arise during this task. We then briefly