Enhancing Navigability: An Algorithm for Constructing Tag Trees

Organizing resources into a hierarchical structure for subject browsing has been recognized as an important tool in information-seeking processes (Golub & Lykke, 2009). A hierarchy can offer searchers information on the collection being searched before any interaction happens. Chen et al. (2012) explored Web resource organization structures based on open-access Web FTP sites. They found that users usually have an upper limit for the depth of the hierarchical structures when organizing resources. With the increasing amount of resources, users preferred to have a flatter structure instead of a deeper one. According to the study, structural complexity needs to be controlled.

Tags are non-hierarchical keywords given by different users to describe information resources. Although unavoidably noisy and ambiguous, these tags reflect the context of the resource domain and the evolution of the knowledge. Thus tags have been widely used in digital resource retrieval, classifications, and summarization. The relationships between tags also facilitate peoples’ understanding of the knowledge of the resource domain. Some studies have tried to generate taxonomies by finding “is-a” or “a-part-of” relationships among concept tags (Si, Liu, & Sun, 2010; Tsui et al., 2010, Verma et al., 2015). Many tags were removed if they were not taken as concepts. Naturally, these taxonomies were not suitable for the purpose of navigation. On the other hand, other studies aimed to develop more loosely structured hierarchies for the purpose of navigating through a large number of resources (e.g. Candan, Di Caro, & Sapino, 2008; Helic et al., 2010; Heymann, & Garcia-Molina, 2006; Huang et al., 2013; Sinclair & Cardew-Hall, 2008). These hierarchies usually involved various tags and were more practical when users were not familiar with the resource domain. This study belongs to this stream and goes further on semantic coherence and structural balance of the hierarchy for the purpose of navigation.

Two aspects are important in developing a tag tree: selecting quality tags as nodes of the hierarchy and inferring reasonable parent-children relationship among the selected tags.

An empirical study on complex dynamics of tagging systems (Halpin, Robu, & Shepherd, 2007) has shown that consensus around stable tag distributions and shared vocabularies did exist, even if there was no central controlled vocabulary. It is suggested that the popular tags used by different people were valuable in understanding a given domain. Therefore many studies used tag frequency as a simple but effective tag selection criterion (e.g. Strohmaier, Körner, & Kern, 2012; Suchanek, Vojnovic, & Gunawardena, 2008).

The hierarchy generation methods need to detect the hidden relationships among tags and organize them to represent the resource domain. The previous approaches proposed in the literature include three types: (1) developing heuristic rules based on natural language processing (NLP) (Tsui et al., 2010); (2) depending on a thesaurus such as Wordnet (Verma et.al., 2015); and (3) using unsupervised methods (Gemmell et al., 2008; Huang et al., 2013; Heymann, & Garcia-Molina, 2006; Luo, & Chen, 2013; Si, Liu, & Sun, 2010; Zhou et al., 2007). The first two types have limitations in some circumstances because of manual cost or the scope of thesauri.

Among the unsupervised methods, hierarchical clustering-based methods (Begelman, Keller, & Smadja, 2006; Gemmell et al., 2008; Zhou et al., 2007) and tag generality-based methods (Heymann, & Garcia-Molina, 2006; Luo & Chen, 2013) were widely used. Clustering-based methods iteratively partitioned the tags into groups and built the tag tree using either bottom-up or top-down approaches. In contrast generality-based methods first ranked the tags by their generality in a flat tag network and then added a tag as a child of its most similar tag that had already existed in the hierarchy. A typical problem in clustering-based methods is the interpretability of a node’s label. Although related tags were hierarchically clustered, it was difficult to determine which one would represent a category naturally. The generality-based methods were mainly derived from the idea of Heymann and Garcia-Molina (2006), who proposed a simple, efficient algorithm for converting a large set of tags into a navigable tag tree (Camiña, 2010).

According to Heymann and Garcia-Molina (2006), tags were first linked in an undirected graph if their similarity is above a predefined similarity threshold. They were then ranked in descending order by their generality, and these ranked tags were added to the tree through comparing their similarity with the present tags in the tree. Note that, in their study, generality of a node was defined as its centrality in a network, which implied the capability of a node to associate with others. The more nodes a tag associates with, the more generality it has. As a result, these methods tried to arrange the nodes of higher generality close to the root when constructing a tag tree. In Helic et al. (2011) and Strohmaier et al. (2012)’s evaluation, the generality-based methods, DegCen/Cooc and ClosCen/Cos, outperformed the clustering-based ones from semantic and navigational perspectives.

In generality-based methods, tag networks could be built based on tag similarity (Heymann & Garcia-Molina, 2006) and co-occurring frequency (Benz et al., 2010), denoted as Cos and Cooc, respectively; the generality of a tag could be measured by its closeness or degree centrality in the network, represented as ClosCen and DegCen. According to Helic et al. (2011) and Strohmaier et al. (2012), the performance of DegCen/Cooc and ClosCen/Cos had no significant difference. However, the DegCen/Cooc combination has a lower computing cost and therefore is more practical. In this case, this study adopted DegCen/Cooc combination as baseline.

Although Heymann’s algorithm and its variations of other studies were considered effective in the above evaluation experiments, there are two issues that have not been solved by either DegCen/Cooc or ClosCen/Cos.

The tag tree constructed by the proposed method is supposed to be a user-friendly navigable tool as well as a domain knowledge markup tool. When exploring in a tag tree, users will always track along the paths that most likely lead them to find their desired information. Thus in each decision, they would take the branch whose name most closely meets their search intention. If none of the names indicates a feasible direction, they probably roll back to an ancestor and restart from another branch, or just abandon the exploration.

Based on the above understanding, we define several desired features:

The nodes in the tree should be representative. A tag is selected as a node in the tree if, (a) it can represent a group of similar tags in terms of meaning; and (b) it has the capability to associate many other nodes in terms of its role in the network.

According to the selection, all the tree nodes collectively will represent the main content of the resource domain as complete as possible. The meaning of sibling nodes should have the least overlap. The judgement cost for users is thus lowered when they face multiple choices. This idea is borrowed from the field of search engines, where diversified retrieval results are kept to illuminate a searcher’s vague searching intention (Agrawal et al., 2009; Carbonell & Goldstein, 1998; Rafiei, Bharat, & Shukla, 2010). The detailed implementation is shown in Algorithm 1 of Section 4.

Algorithm 1

Get representative nodes from tag set L.

The relationship between nodes should be reasonable and intuitive. This means that the semantic meaning along a path keeps coherent with as little drift as possible. In addition, the meaning from parent nodes to their children should be increasingly fine-grained.

For arbitrary node tⁱ, i denotes the depth of the node in the tree, and its siblings compose set Bi={b0i,b1i,…<!-- ? -->bli,…<!-- ? -->,bsi},l∈<!-- ? -->[0,s].$ B^i = \{b_0^i,\, b_1^i,\, \ldots\, b_l^i,\,\ldots,\, b_s^i\}, \,l\,\in [0, s]. $ The path from root to t is represented as root→t¹→t²→…→tⁱ. For example in Figure 1, the path of a node t³ is root→t¹→t²→t³.

Figure 1

To keep semantic coherence, the similarity between the nodes in level j (j ∈ [1, i-1]) with tⁱ is: sim(tj,ti)≥<!-- = -->sim(blj,ti),wherel∈<!-- ? -->[0,s],j∈<!-- ? -->[1,i−<!-- - -->1].$$ \text{sim}(t^j,\, t^i) \geq sim(b_l^j, \,t^i),\quad where \,\,l \,\in\, [0, \,s],\, j \,\in\, [1,\, i-1]. $$(1)

Equation (1) denotes that the similarity between tⁱ and its ancestor t^j should be no less than that of the sibling of t^j with tⁱ. In Figure 1, take t³ as an example, the similarity between t³ and t¹ is bigger than t³ with each member of B¹. So is t³ and t² with t³ and B². This criterion ensures semantic coherence not only along a top-down path, but also among the range of children sets to their parents.

In order to enhance the navigability of the tag tree, representative nodes need to be selected by similarity and generality.

Given a resource set R, there is a set of associated tags T. The similarity of two tags can be calculated by the cosine of the two vectors. If two tags have been used together in annotating a resource, they probably have a certain association with each other. The higher frequency of their co-occurrence, the stronger their relationship is. If the similarity or co-occurrence frequency of two tags is bigger than the given threshold, there is an edge between them. Thus, the tags form a weighted graph. Heymann and Garcia-Molina (2006) built their tag network by tag similarity, and Benz et al. (2010) by co-occurrence.

In this article, a tag network was built by co-occurrence in order to compare with the well-established solution DegCen/Cooc, according to Helic et al. (2011) and Strohmaier et al. (2012). And the generality of a tag was measured by h-degree.

In a weighted network, the h-degree of a node is defined as h if h is the largest natural number such that the node has at least h links each with strength at least equal to h (Rousseau & Zhao, 2015; Zhao, Rousseau, & Ye, 2011). The h-degree is considered more suitable for weighted networks than indicators based on the underlying unweighted network, for example, degree, since it reflects more information about the links’ strength and structure.

Given a tag t, if at most h of its neighbours co-occur(s) with t at least h times each, the h-degree of t is h. Its neighbours are sorted in descending order by their co-occurrence frequency with t, and then t’s h-degree is identified. The higher h-degree t has, the more popular implication it has.

The difference between h-degree and degree centrality is that the former measures the generality of a node from its salient semantics while the latter just counts all co-occurrence between t and other tags regardless of whether the co-occurrence was caused by individuality. Considering the pervasive individuality in social annotation circumstances, we believed h-degree could better detect salient generality. In the experiment in Section 5.2, we will compare h-degree with degree centrality in their effectiveness in nodes selection.

Representativeness in Feature (1) in Section 3.1 is different from the generality. It is determined by generality and similarity in the proposed method. Nodes of high representativeness will be assigned close to the root. Yet a general node is not necessarily representative if it is very similar to an existing representative node.

Selecting the representative nodes involves the judgement of both similarity and generality. Initially, the node of max generality is chosen from a given tag set, and the rest of the nodes are punished according to their similarity to it. The punishment is to keep diversity among siblings and avoid overlapping semantic boundary in each level, as discussed in Feature (1) in Section 3.1.

In Algorithm 1, L is the initial input tag set; k is a pre-defined maximum number of child nodes under a particular parent; and λ denotes the punishment factor based on similarity. The selected representative nodes will be put into set A as output, which is initially empty.

At first, the input tag set L is assigned to T. The function Ge(t) gets generality for each tag in T and stores them in an array D. The generality refers to the degree centrality or h-degree of a tag in the discussed network. The tag of maximum generality selected in Line 5 is moved from T to the representative node set A in Line 6, and T shrinks gradually. In Line 7 to Line 9, the remaining nodes in T are punished based on their similarity to the selected representative node. In each iteration, at most k representative nodes are selected.

In Algorithm 2, p is the pointer to parent node; L, k, and λ have been introduced in Algorithm 1. The tree is built bottom-up by recursively assigning nodes to its similar representative node.

Algorithm 2

Construct a tag tree.

In each iteration, the representative tags (at most k) are selected from L to A in Line 1. The remaining nodes are divided into groups based on their similarity to nodes in A from Line 7 to Line 9. A sub-tree is built from the nodes of the group, and added to its representative node as its children in Line 11 to Line 15.

If the generality of a node L[i] is bigger than that of the representative node A[i], it will be discarded and will not be taken as a descendant node of A[i], see Line 8. This is to ensure the increasingly fine-grained parent-child relationship, discussed as Feature (2) in Section 3.1. The downside is that some non-representative nodes might be absent from the hierarchical structure. One solution could be first maintaining a list with the discarded nodes, then rerunning the algorithm and organizing them into an additional hierarchy that is then appended to the root as additional branches of the folksonomy.

The tag similarity comparison has been involved in Line 7 of Algorithm 2 and Line 8 in Algorithm 1. Cosine similarity is applied to tag frequency vectors to compare their relationships.

The experiment was conducted using dataset PINTS

https://west.uni-koblenz.de/en/forschung/datensaetze/pints-experiments-data-sets

The biggest challenge in evaluating the navigation of a tag tree is the lack of a baseline. The difficulty is mainly because the resources may come from different domains, and the hierarchies can be generated for different purposes. Researchers compared the auto-generated tag hierarchy against those well-accepted taxonomies in certain resource domains, such as Wordnet, Yago, and Wikitaxonomy. (Strohmaier et al., 2012). In comparing taxonomy generation techniques, Camiña (2010) has proposed several criteria to help develop the evaluation methodology. However, we need to keep in mind that taxonomy serves to represent a logical model of the knowledge domain with precise concepts, instances, and their relationships, rather than facilitating users’ browsing behavior by adapting to a given resource set.

The baseline hierarchy is the Open Directory Project (ODP)

http://www.dmoz.org/

Each c in AT has t_p for the precision of the node with regard to RT, and t_r for the recall. In addition, TP (Taxonomic Precision), TC (Taxonomic Recall), and F1 (Taxonomic F1) measure the average resemblance between the generated hierarchy and the baseline taxonomy.

Given node c∈C_AT ∩ C_RT, tp(c,AT,RT)=|ce(c,AT)∩<!-- n -->ce(c,RT)||ce(c,AT)|,$$ \displaystyle tp(c,\,AT, \,RT)=\frac{|ce(c,\,AT)\cap ce(c,\,RT)|}{|ce(c,\,AT)|}, $$(2)tr(c,AT,RT)=|ce(c,AT)∩<!-- n -->ce(c,RT)||ce(c,RT)|,$$ \displaystyle tr(c,\,AT, \,RT)=\frac{|ce(c,\,AT)\cap ce(c,\,RT)|}{|ce(c,\,RT)|}, $$(3)

For the whole tree AT, TP, and TR are based on the contribution of t_p and t_r from each c. TP(AT,RT)=1|CAT∩<!-- n -->CRT|∑<!-- ? -->c∈<!-- ? -->|CAT∩<!-- n -->CRT|tp(c,At,RT),$$ \displaystyle TP(AT,\,RT)=\frac{1}{|C_{AT}\,\cap\, C_{RT}|}\sum\limits_{c\in|C_{AT}\,\cap\, C_{RT}|}tp(c,\,At,\,RT), $$(4)TP(AT,RT)=1|CAT∩<!-- n -->CRT|∑<!-- ? -->c∈<!-- ? -->|CAT∩<!-- n -->CRT|tr(c,At,RT),$$ \displaystyle TP(AT,\,RT)=\frac{1}{|C_{AT}\,\cap\, C_{RT}|}\sum\limits_{c\in|C_{AT}\,\cap\, C_{RT}|}tr(c,\,At,\,RT), $$(5)F1(AT,RT)=2×<!-- ? -->TP(AT,RT)×<!-- ? -->TR(AT,RT)TP(AT,RT)+TR(AT,RT).$$ \displaystyle F1(AT, \,RT)=\frac{2\times \,TP(AT, \,RT)\times \,TR(AT, \,RT)}{TP(AT, \,RT)+ TR(AT, \,RT)}. $$(6)

5.2.1

HTT vs. NTT Algorithms

We calculated the TP, TR, and F1 metrics against the ODP classification for both HTT and NTT. In Figure 2, the left part is the results using degree centrality for generality, and the right part is those of h-degree. The x-axis denotes punishment parameter λ in the proposed algorithm, and the vertical axis of each line of diagram represents TP, TR, and F1, respectively. The bar in position 0 on the x-axis of each diagram represents the value of HTT algorithm, and the other following positions demonstrate the values of NTT algorithm with different λ values. When λ changes from 0.1 to 1.0, there are 10 groups of bars. In each group, the bars from the left to the right show the effects of structural controlling parameter k, i.e. the TP or TR or F1 when k is assigned as 10, 20, 30, 40, and 50.

Figure 2

Since a tag might be found in multiple ODP branches (e.g. the tag “Sports” appears in both paths “Arts/Movies/Genres/Sports” and “Business/Arts_and_ Entertainment/Sports”), the final t_p value of a tag is the average of the t_p values of all the paths. So is t_r.

The TP values of h-degree are higher than those of degree centrality, which means the h-degree is superior to degree centrality as a node generality metric. When the structure parameter k is set from 30 to 50, the results of TP, TR, and F1 are far better than those of when k is 10 or 20. In addition, when λ is 0.4, the TP value of NTT reaches its highest point no matter with degree centrality or h-degree.

Since the F1 value of NTT reaches its maximum when X = 0.4 and k = 30, the conditions of NTT are set to h-degree with parameters λ = 0.4 and k = 30 by default in this experiment dataset. Under this condition, the TP of NTT is much higher than that of HTT, suggesting a better overlap with the ODP paths, which is likely due to the consideration of the semantic coherence in NTT.

Two visualized fragments of NTT and HTT are illustrated in Figures 3 and 4. The structure of the HTT tree is not balanced as well as is the NTT tree. For example, at the second level under the root, almost all the tags were considered more similar to the node “software” than “buptsse” by the HTT algorithm. However, in NTT tree, tags were more evenly distributed into different parents to avoid the structural skew.

Figure 3

Figure 4

In addition, the algorithm of HTT is likely to lead to semantic drift. For example, the tags “news,” “games,” and “health” in the HTT tree are located respectively in the path of “/software/tools/web/design/blog/news,” “/software/tools/web/design/cool/fun/games” and “/software/tools/productivity/lifehacks/health.” If users want to look for resources of news, they will never expect to start from “software” to locate these tags. The problem of semantic drift may hurt the navigability of the hierarchy. However, in the NTT hierarchy, the same tags “news,” “games,” and “health” are not under a particular parent according to their representativeness. Instead, they act as heads of a group of branches and are listed directly under the root node, which is easier for users to find.