# Graph-Based Taxonomic Semantic Class Labeling
## 3 Graph-Based Taxonomic Semantic Associative Community Labeling
### Dependency-Based Taxonomic Semantic Class Labeling
#### 3.2.1 Dependency-Based Labeling: Procedure Description
More precisely, the set of its nodes is the set of community lexeme nodes \(c_{1},\ldots,c_{n}\), and the elements of each \(H_{j}^{k}\), i.e., \(k\) top-ranked _is_a_ collocates of each lexeme \(c_{j}\) in the lexical subgraph:  
\[V_{L}:=\{c_{1},\ldots,c_{n}\}\cup H_{1}^{k}\cup\ldots\cup H_{n}^{k}.\]  
The edges of \(G_{L}\) and their weights are defined according to the chosen collocation measure \(f\) and the selection performed:  
\[E_{L}:=\bigcup_{j=1}^{n}\ \{\ (c_{j},h)\ |\ h\in H_{j}^{k}\},\ \ \ \ w(e):=f(e),\ e\in E_{L}.\]  
The set of edges \(E_{L}\) is obtained as the union of the edges incident to each of the lexemes \(c_{j}\), from the clustered coordination community \(\text{FoF}[and|or]_{j}^{s}\). In this way, for each lexeme \(c_{j}\) in the lexical subgraph, we include the edges \((c_{j},h)\) which point from the lexeme \(c_{j}\) to its collocate \(h\), according to the direction of the _is_a_ syntactic-semantic relation. In addition, the edge weights reflect the lexical graph properties and indicate which links between nodes in the graph \(G_{L}\) are more important than others according to the collocation measure \(f\). Step (iii): Community labels are selected among the in nodes of the label graph \(G_{L}\). For this purpose, the label importance score, \(I_{L}\), is defined for the in nodes of \(G_{L}\), \(h\), taking into account their weighted in degree and the \(SLI\) centrality score of the corresponding out node in the \(\text{FoF}[and|or]_{s}\) graph:  
\[I_{L}(h):=\sum_{ \begin{subarray}{c}c\in E_{L}\\ e=(c)h\end{subarray} }w(c,h)\cdot SLI(c)^{2}=\sum_{(c,h)\in E_{L}}f(h)\cdot SLI (c)^{2}.\]  
According to the above definition, all directed edges \(e=(c,h)\) from the graph \(G_{L}\), \(e\in E_{L}\), pointing to the lexeme \(h\), contribute to the label importance score of the lexeme node \(h\). This is achieved through the corresponding edge weights. The higher the total weight of the incoming edges, the higher the importance of the label node. Furthermore, we take into account the centrality of the corresponding outgoing nodes. For each lexeme \(c\) incident to the \(h\) we multiply the edge weight \(w(c,h)\) with \(SLI(c)^{2}\), strongly emphasizing the importance of the lexeme node \(c\) in the graph representation of the lexical community \(\text{FoF}[and|or]^{s}\). Since \(SLI\) indicates the strength of integration of the nodes into the graph clusters, we use it as a crucial tool to highlight the best label candidates in our labeling task. To strongly emphasize the influence of the most integrated nodes in the community, the squared values of the \(SLI\) scores feature in the related label importance score. In this way, the collocated nodes that are highly integrated into the subnetwork structure, receive high label importance scores and are therefore the best candidates for label selection. The lexeme nodes with the highest label importance score, \(I_{L}\), typically one of two lexemes, are selected as labels of the given community. Note that, as shown in Figure 2, some of the lexemes \(c_{j}\) from the coordination community may share some of the selected _is_a_ collocates, i.e., target the same lexeme node. Therefore, the sets \(H_{j}^{k}\) are not necessarily pair-wise disjoint. Note also that some of the lexemes \(c_{j}\) may themselves appear as elements of \(H_{j}^{k}\) sets, i.e., lexeme nodes from the coordination community may appear as label candidates. The sequential nature of the procedure allows a parametrization of the label selection with regard to the lexeme nodes from the underlying semantic fields. One of the options is to exclude lexemes that are not in the FoF\([and|or]_{s}\) coordination graph. This restriction allows a more meronymic (part-whole) relationship between the labels. Another option is to exclude lexemes of a coordination cluster FoF\([and|or]_{i}^{s}\), designated for taxonomic labeling, to appear as label candidates. In this way, the label is not chosen from a set of expressed lexemes in a semantic field.