guarantee that the final graph is in a tree form. In particular, for a certain exemplar, we sort its members by their message summation value in descending order. Note that the higher the value, the more likely the node belongs to its exemplar.

The parent exemplar of a cluster of nodes is determined as follows. If the exemplar of the cluster is a leaf node, the parent exemplar of the cluster is the parent exemplar of the exemplar. Otherwise, the parent exemplar of the highestranked leaf node will be chosen. We then split all member nodes that have different parent exemplars to that of the cluster. Note that a more sophisticated approach to this task may be applied: e.g., once split, find the next best valid exemplar to join. However, this more complex procedure is very cumbersome - the decision to re-join a certain cluster may recursively result in the invalidity of other clusters.

## Validation On A Toy Example

To evaluate the utility of RAP, we first apply it to a simplified data set, which consists of a small fraction of the personal hierarchies taken from the Flickr data set described in (Plangprasopchok and Lerman 2009). These hierarchies are about
'animal', 'pet', 'wildlife', 'bird' (wild and domestic), which are very similar to Figure 1(b). The ideal integrated hierarchy is similar to Figure 1(a), where 'bird' concept is split into domestic and wildlife birds under the 'animal' concept.

There are total of 96 saplings generated by different users in this data set.

We quantitatively compare the quality of the tree learned by RAP against that learned by the standard AP algorithm.

In addition, since the AP does not have machinery for "correcting" the output graph into a tree, after the final inference step, we run the same procedure that recovers exemplars and valid cluster assignments that is used in the final step of RAP.

We used the following evaluation metrics: net similarity and tree depth and bushiness. Intuitively, we prefer "a tree of exemplars," which clusters as many similar nodes as possible
(high net similarity), as well as a comprehensive tree (bushy and deep).

We used a simple similarity function, S(**i, j**), to compute the similarity between two nodes i and j. Let t ij be a number of common tags of i and j nodes. If i and j have the same stemmed name, S(i, j) = min(1.0, tij) (if they have, at least, just one tag in common, the similarity value goes to 1); otherwise, 0. The damping factor is set to 0.9, and the number of iterations is set to 4, 000. The preference is set to 0.**0001** uniformly.

The inference converges in both approaches before 4, 000 iterations and returns a single 'animal' tree. The net similarities of the trees (after correcting the graphs) are 83.41 (AP)
and 106.31 (RAP). Both approaches return trees of similar depth, namely 3. The distribution of the number of exemplars at depths h0, 1, 2, 3i for AP and RAP are h1, 25, 30, 9i and h1, 2, 32, 12i respectively, and the distribution of the number of instances (data points) at depths h0, 1, 2, 3i are h35, 78, 46, 10i for AP, and h35, 81, 51, 13i for RAP. Although AP yields a "bushier" tree of exemplars, this does not really demonstrate its superiority to RAP. In fact, at the depth 1, AP shatters the 'pet' concept into many singleton

![0_image_0.png](0_image_0.png)

Figure 4: trees induced by AP(a) and RAP(b). The numbers in brackets just indicate the index numbers of the exemplar nodes of their clusters. Non-exemplar nodes are collapsed to one of these exemplars. The nodes without number are those that cluster all nodes with the same name together.

clusters; while RAP nicely merges them into a single cluster. The distribution of the number of instances at different depths also indicates that RAP can aggregate more nodes into a tree, compared to AP. Hence, RAP's overall quality on this small example is higher.

The trees learned by both methods are shown in Figure 4.

AP clusters both wild and domestic 'bird' nodes together in cluster number 50 as illustrated in Figure 4(a), while, RAP separates them into two different clusters: cluster number 16
(wild bird) and cluster number 55 (domestic bird). By taking structural constraints into account, RAP is able to separate 'bird' into different senses. Specifically, during the inference process this constraint prevents all bird nodes from being clustered together, because this will create paths to this cluster from two different parent clusters: 'wildlife' and 'pet'. The only valid configuration then is to have two 'bird' clusters: one under 'wildlife' and one under 'pet'. The inference process optimizes the tree within this valid configuration. AP, on the other hand, does not have this machinery and, consequently, merges all 'bird' nodes together without concern for where the incoming links come from. The final correction step does not optimize the tree structure, and the tree learned by AP is worse than one learned by RAP.

## Validation On Real-Wold Data

We also compared RAP against AP on the data collected from Flickr (Plangprasopchok and Lerman 2009). We manually selected 15 seed terms, and for each term used the following heuristic to obtain "relevant" saplings. First, we selected saplings whose root names were similar to the seed term. We then used the leaf node names of these saplings to select other saplings whose root names were similar to these names, and so on, for the total of two iterations. We used the settings described above but with the number of itera-