
| Whole folksonomies   | Comparison with ODP        | Manual                                             |                                   |                                  |                                 |                           |                       |                 |               |               |     |     |     |     |
|----------------------|----------------------------|----------------------------------------------------|-----------------------------------|----------------------------------|---------------------------------|---------------------------|-----------------------|-----------------|---------------|---------------|-----|-----|-----|-----|
| #leaves              | AUT                        | #ovlp lvs                                          | fmTO                              | LR                               | AUT                             | Acc (10%)                 |                       |                 |               |               |     |     |     |     |
| seeds                | sig                        | sap                                                | sig                               | sap                              | sig                             | sap                       | sig                   | sap             | sig           | sap           | sig | sap | sig | sap |
| anim                 | 268                        | 583 694.0 1076.0 68                                | 92 0.602 0.659 0.281 0.360 160.0  | 189.5 0.89 0.74                  |                                 |                           |                       |                 |               |               |     |     |     |     |
| bird                 | 73                         | 103                                                | 84.5                              | 113.5 20                         | 22 0.760 0.755 0.281 0.315 21.5 | 28.5 0.60 1.00            |                       |                 |               |               |     |     |     |     |
| invertebr            | 11                         | 15                                                 | 15.5                              | 19.5                             | 3                               | 1 0.762 1.000 0.250 0.125 | 4.5                   | 1.5 1.00 1.00   |               |               |     |     |     |     |
| vertebr              | 80                         | 114 162.5                                          | 236.5                             | 1                                | 0 1.000                         | n/a 0.600 0.200           | 2.5                   | n/a 1.00 1.00   |               |               |     |     |     |     |
| insect               | 29                         | 44                                                 | 35.5                              | 61.5                             | 5                               | 5 0.924 0.924 0.857 0.857 | 6.5                   | 6.5 1.00 1.00   |               |               |     |     |     |     |
| fish                 | 7                          | 6                                                  | 7.5                               | 6.5                              | 0                               | 0                         | n/a                   | n/a 0.016 0.016 | n/a           | n/a 1.00 1.00 |     |     |     |     |
| plant                | 110                        | 194 265.5                                          | 426.0                             | 6                                | 7 0.613 0.735 0.250 0.273 13.0  | 11.5 0.67 1.00            |                       |                 |               |               |     |     |     |     |
| flora                | 64                         | 403 173.0 1048.5                                   | 6                                 | 18 0.483 0.481 0.130 0.407 16.0  | 84.0 1.00 1.00                  |                           |                       |                 |               |               |     |     |     |     |
| fauna                | 141                        | 609 420.0 1146.0                                   | 9                                 | 31 0.463 0.490 0.113 0.212 27.0  | 71.5 0.91 0.85                  |                           |                       |                 |               |               |     |     |     |     |
| flower               | 112                        | 169 210.5                                          | 226.5                             | 1                                | 1 0.379 1.000 0.267 0.250       | 3.5                       | 1.5 1.00              | n/a             |               |               |     |     |     |     |
| reptil               | 3                          | 4                                                  | 4.5                               | 4.5                              | 2                               | 3 0.625 0.622 0.500 0.667 | 2.5                   | 3.5 n/a         | n/a           |               |     |     |     |     |
| amphibian            | 1                          | 1                                                  | 1.5                               | 1.5                              | 1                               | 1 1.000 1.000 1.000 1.000 | 1.5                   | 1.5 n/a         | n/a           |               |     |     |     |     |
| build                | 7                          | 23                                                 | 11.5                              | 37.5                             | 0                               | 0                         | n/a                   | n/a 1.000 1.000 | n/a           | n/a 1.00 1.00 |     |     |     |     |
| urban                | 6                          | 80                                                 | 15.0                              | 145.5                            | 0                               | 0                         | n/a                   | n/a 0.071 0.071 | n/a           | n/a 1.00 1.00 |     |     |     |     |
| countri              | 378 1605 798.5 4504.0      | 2                                                  | 4 0.447 0.665 0.143 0.214         | 8.0                              | 8.5 1.00 1.00                   |                           |                       |                 |               |               |     |     |     |     |
| africa               | 53                         | 71                                                 | 90.5                              | 119.5 23                         | 27 0.773 0.895 0.508 0.547 37.5 | 40.5 1.00 1.00            |                       |                 |               |               |     |     |     |     |
| asia                 | 187                        | 284 389.0                                          | 631.5 80                          | 85 0.734 0.788 0.396 0.484 165.5 | 168.5 1.00 1.00                 |                           |                       |                 |               |               |     |     |     |     |
| europ                | 379 1073 916.0 2706.5 165  | 301 0.619 0.670 0.236 0.418 369.0                  | 874.5 1.00 0.94                   |                                  |                                 |                           |                       |                 |               |               |     |     |     |     |
| south africa         | 12                         | 17                                                 | 15.5                              | 18.5                             | 3                               | 3 0.431 0.600 0.444 0.444 | 3.5                   | 3.5 0.78 1.00   |               |               |     |     |     |     |
| north america        | 166                        | 731 435.0 2203.5 67                                | 118 0.545 0.576 0.165 0.319 170.5 | 361.5 1.00 0.92                  |                                 |                           |                       |                 |               |               |     |     |     |     |
| south america        | 32                         | 50                                                 | 54.5                              | 101.5 12                         | 15 0.706 0.832 0.415 0.463 20.5 | 28.5 1.00 1.00            |                       |                 |               |               |     |     |     |     |
| central america      | 27                         | 8                                                  | 53.5                              | 12.5                             | 1                               | 2 0.631 0.754 0.417 0.500 | 2.5                   | 4.5 1.00 1.00   |               |               |     |     |     |     |
| unit kingdom         | 106                        | 267 274.5                                          | 658.5 31                          | 82 0.787 0.724 0.099 0.127 71.5  | 179.5 1.00 1.00                 |                           |                       |                 |               |               |     |     |     |     |
| unit state           | 102                        | 375 217.0                                          | 936.5 35                          | 55 0.620 0.749 0.130 0.256 74.5  | 122.0 1.00 1.00                 |                           |                       |                 |               |               |     |     |     |     |
| world                | 545 3177 1437.0 9235.0 191 | 475 0.476 0.461 0.085 0.215 490.0 1676.5 0.97 0.96 |                                   |                                  |                                 |                           |                       |                 |               |               |     |     |     |     |
| citi                 | 123                        | 448 234.0                                          | 927.5                             | 0                                | 0                               | n/a                       | n/a 0.111 0.100       | n/a             | 2.5 1.00 1.00 |               |     |     |     |     |
| craft                | 5                          | 1                                                  | 10.5                              | 1.5                              | 1                               | 0 0.603                   | n/a 0.056 0.050       | 2.5             | n/a 1.00      | n/a           |     |     |     |     |
| dog                  | 15                         | 26                                                 | 17.5                              | 28.5                             | 0                               | 1                         | n/a 1.000 0.045 0.080 | n/a             | 1.5 n/a       | n/a           |     |     |     |     |
| cat                  | 11                         | 39                                                 | 13.5                              | 41.5                             | 0                               | 0                         | n/a                   | n/a 0.100 0.100 | n/a           | n/a n/a       | n/a |     |     |     |
| sport                | 207                        | 74 407.0                                           | 86.5 19                           | 27 0.693 0.647 0.091 0.084 30.0  | 31.5 0.28 1.00                  |                           |                       |                 |               |               |     |     |     |     |
| australia            | 47                         | 83                                                 | 71.0                              | 147.5 12                         | 27 0.354 0.665 0.123 0.216 14.5 | 36.5 0.67 1.00            |                       |                 |               |               |     |     |     |     |
| canada               | 55                         | 763 128.0 2502.0 11                                | 27 0.620 0.587 0.158 0.241 21.5   | 75.5 1.00 1.00                   |                                 |                           |                       |                 |               |               |     |     |     |     |

Table 2: This table presents empirical validation on folksonomies induced by the proposed approach, sap, comparing to the baseline approach, sig**. The first column group presents properties of the whole induced**
trees: the number of leaves and Area Under Tree(AUT). The second column group reports the quality of induced trees, relatively to the ODP hierarchy. The metrics in this group are **modified Taxonomic Overlap**
(fmTO) (averaged using Harmonic Mean), Lexical Recall (LR**), where their scales are ranging from** 0.0 to 1.0 (the more the better), as AUT is computed from portions of the **trees, which are comparable to ODP.**
"\#ovlp lvs" stands for a number of overlap leaves (to ODP). The last column group reports performance on manually labeled portions of the trees, which do not occur **in ODP. In some cases, "n/a" exists since we**
cannot compute its corresponding value.

lows similar concepts to appear multiple times within the same hierarchy. For example, sap allows the anim folksonomy to have both anim → pet → cat and anim → **mammal**
→ cat **paths, while only one of these paths is retained by**
sig**. Last,** sap **can identify synonyms from structure (loops).**
We learned the following synonyms from Flickr data: {**anim**, creatur, critter, all anim, wildlife} and {insect, bug}.

## 6. Related Work

Constructing ontological relations from text has long interested researchers, e.g., [6, 16, 19]. Many of these methods exploit linguistic patterns to infer if two keywords are related under a certain relationship. However, these approaches are not applicable to social metadata because it is usually ungrammatical **and much more** inconsistent **than natural language text.**
Several researchers have investigated various techniques to construct conceptual hierarchies from social metadata.

Most of the previous work utilizes tag statistics as evidence.

Mika [10] uses a graph-based approach to construct a network of related tags, projected from either a user-tag or object-tag association graphs; then induces broader/narrower relations using betweenness centrality and set theory. Other works apply clustering techniques to tags, and use their cooccurrence statistics to produce conceptual hierarchies [3].

Heymann and Garcia-Molina [7] use centrality in the similarity graph of tags. The tag with the highest centrality is considered more abstract than one with a lower centrality; thus it should be merged to the hierarchy first, to guarantee that more abstract nodes are closer to the root. Schmitz [15]
applied a statistical subsumption model [14] to induce hierarchical relations among tags. Since these works are based on tag statistics, they are likely to suffer from the "popularity vs. generality" problem, where a tag may be used more frequently not because it is more general, but because it is more popular among users.

Our present work, sap**, is different from our earlier approach,** sig **[12] in many aspects. First,** sap **exploits more**
evidence, i.e., structure and tag statistics of personal hierarchies rather than individual relations' co-occurrence statistics as in sig**. Second,** sap **is based on the relational clustering approach that incrementally attaches relevant saplings**
to the learned folksonomies, as sig **exhaustively determines**
the best path out of all possible paths from the root node to a leaf, which is computationally expensive when the learned