
## Tions Limited To **2000**.

For each seed, we ran AP and RAP on all extracted saplings; then measured the net similarity of the induced tree. For measuring the induced tree's structure in terms of bushiness and depth, we introduce a simple, yet intuitive measure, namely Area Under Tree(AUT), which takes both tree bushiness and depth into account. To calculate AUT for a given tree, we plot the distribution of the number of nodes at each level and then compute the area under the plot. Intuitively, trees that keep branching out at each level will get a larger AUT than those that short and thin. Suppose that we have a tree in which the number of nodes at 1 st and 2 rd level are 3 and 4, respectively. With the scale of tree depth set to 1.0, AUT of this tree would be 0.5 × (1 + 3) + 0.5 × **(3 + 4) = 5**.5.

| Entire Set         | Induced Seed Trees                          |            |               |              |           |         |
|--------------------|---------------------------------------------|------------|---------------|--------------|-----------|---------|
| Net Sim            | # Trees Best Tree's Net Sim Best Tree's AUT |            |               |              |           |         |
| AP                 | RAP                                         | AP RAP AP  | RAP           | AP           | RAP       |         |
| africa             | 46.93                                       | 103.92 2   | 2             | 25.41 63.31  | 55        | 103     |
| animal             | 3609.32 3839.88 4                           | 4          | 142.48 156.28 | 606          | 727       |         |
| asia               | 474.06 617.15 2                             | 2          | 143.75 219.86 | 445.5 523.5  |           |         |
| australia          | 167.65 227.24 2                             | 2          | 72.11 123.41  | 104          | 151       |         |
| bird               | 231.73 365.02 3                             | 3          | 31.11 33.31   | 75           | 71.5      |         |
| canada             | 278.7                                       | 312.29 2   | 2             | 46.32 50.62  | 127       | 138     |
| craft              | 235.65 285.75 6                             | 6          | 24.31 24.41   | 72.5 67.5    |           |         |
| fish               | 124.83 132.43 1                             | 1          | 44.61 45.71   | 69           | 68.5      |         |
| insect             | 244.69 257.19 31 31                         | 34.81 37.1 | 66.5 63       |              |           |         |
| invertebrate 34.01 | 56.2                                        | 1          | 1             | 32.91 55.11  | 97.5 99.5 |         |
| mammal             | 97.86                                       | 117.25 2   | 2             | 50.71 36.71  | 58.5 65   |         |
| plant              | 565.72 714.7                                | 2          | 2             | 12.3         | 13.4      | 19.5 19 |
| sport              | 725.81 758.2                                | 9          | 9             | 92.85 105.74 | 269       | 252.5   |
| uk                 | 640.48 754.16 1                             | 1          | 370.84 526.7  | 633          | 673.5     |         |
| usa                | 286.28 390.56 1                             | 1          | 244.29 341.99 | 354.5 370    |           |         |

Table 1: The table presents the performance comparisons between AP and RAP by the net similarity for the entire data and the best induced tree (with highest net similarity) on 15 different seed sets. The number of induced trees and Area Under Tree (AUT) are also reported.

Both quantitative and manual inspections confirm the advantages of RAP over AP. As shown in Table , RAP yields better net similarity in all cases. Although both approaches return the same number of trees, RAP appears to better cluster similar nodes in all but one case, namely 'mammal'. In terms of AUT, though many trees are of similar quality, in cases where significant differences exist, they are in RAP's favor. Manual inspection reveals that AP tends to "shatter" trees into isolated singletons rather than merge similar nodes together, as RAP does.

## Related Work

Affinity propagation has been applied to many clustering problems, e.g. segmentation in computer vision (Lazic et al. 2009). It provides a natural way to incorporate constraints while simultaneously improving the net similarity of the cluster assignments, which is not trivial to handle in standard clustering techniques. In addition, no strong assumption is required on the threshold, which determines whether clusters should be merged or not. Moreover, the cluster assignments can be changed during the inference process as suggested by the emergence of exemplars. Nevertheless, to our knowledge, there is no extension of AP algorithm to learn tree structures from many sparse and shallow trees as presented in this work.

There are many other SRL approaches that are applicable as well. For example, Markov Logic Networks
(MLN) (Richardson and Domingos 2006), a generic framework for solving probabilistic inference problems, may also be applied to folksonomy learning, by translating similarity function as well as constraints into predicates.

Since our similarity function is continuous, hybrid MLN
(HMLN) (Wang and Domingos 2008) would be required. The AP framework has advantages due to its simplicity; however we plan to investigate more comparative work with existing SRL approaches, especially as we explore more complex similarity functions.

## Discussion And Conclusion

In this paper, we introduce relational affinity propagation
(RAP), an extension to affinity propagation to learn structures from data by incorporating structural constraints. RAP
optimizes the net similarity and it uses the structural constraint to find good solutions within a space of "valid" solutions. Thus, the final net similarity of the tree learned by RAP is better than AP. Our validations on toy and real-world data support this claim. For the future work, we would like to apply more sophisticated similarity function, which utilizes class labels as in a collective relational clustering approach in order to improve the quality of the learned structures. In addition, the structural constraints can be modified to guide RAP to induce other classes of graphs, e.g., a DAG.

We would also like to extend RAP to apply on other structure learning problems.

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

## References

Bishop, C. M. 2006. *Pattern Recognition and Machine Learning*. Springer-Verlag. Euzenat, J., and Shvaiko, P. 2007. *Ontology Matching*. Springer-Verlag.

Frey, B. J., and Dueck, D. 2007. Clustering by passing messages between data points. *Science* 312:972–976. Givoni, I. E., and Frey, B. J. 2009. A binary variable model for affinity propagation. Neural Comput 21(6):1589–1600. Golder, S. A., and Huberman, B. A. 2006. Usage patterns of collaborative tagging systems. *J. Inf. Sci.* 32(2):198–208.

Kschischang, F.; Frey, B. J.; and Loeliger, H.-A. 2001. Factor graphs and the sumproduct algorithm. *IEEE Transactions on Information Theory* 47:498–519.

Lazic, N.; Givoni, I.; Frey, B.; and Aarabi, P. 2009. Floss: Facility location for subspace segmentation. In *Proceedings of the International Conference on Computer* Vision.

Plangprasopchok, A., and Lerman, K. 2009. Constructing folksonomies from userspecified relations on flickr. In *Proceedings of the World Wide Web conference*.

Richardson, M., and Domingos, P. 2006. Markov logic networks. *Mach. Learn.* 62:107–136. Wang, J., and Domingos, P. 2008. Hybrid markov logic networks. In *Proceedings* of Association for the Advancement of Artificial Intelligence.