# 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  
The ConGraCNet graph construction procedure of the _is_a_-type label graph for an associated lexical cluster consisting of the following steps:  
1. For each lexeme node \(c_{j}\) in the clustered coordination community FoF\([and|or]_{i}^{s}\) with lexemes \(c_{1},\ldots,c_{n}\), a number, \(k\), of the top-rated collocates in the [lexemex\({}_{c_{j}}\) is_a lexemex\({}_{h}\)] and [lexeme\({}_{h}\) is_a lexeme\({}_{c_{j}}\)] relations is identified from a selected corpus;
2. A weighted, first-order (source-friend) directed graph \(F[is\_a]_{i}^{s}\) of identified lexical _is_a_ collocates of the clustered coordination community FoF\([and|or]_{i}^{s}\) is constructed;
3. The most prominent in nodes in the \(F[is\_a]_{i}^{s}\) graph are identified. The obtained graph is used to predict the categorically abstract label of the corresponding lexical cluster from the list of most central lexical nodes in the label graph. We now describe the procedure in detail. Step (i) Given a coordination lexical graph FoF\([and|or]_{s}\) and its clustered coordination community FoF\([and|or]_{i}^{s}\) with lexemes \(c_{1},\ldots,c_{n}\), a corpus C and a parameter \(k\), we extract the collocates, \(h\), of each of the lexemes \(c_{j}\) on the basis of the _is_a_ syntactic-semantic dependency:  
\[H_{j}:=\{\,h\mid[c_{j}\text{ is\_a}\,h]\text{ appears in }C\}\cup\{\,h\mid[h \text{ is\_a}\,c_{j}]\text{ appears in }C\},\ j\in\{1,\ldots,n\}.\]  
That is, to each lexeme \(c_{j}\) from the lexical subgraph FoF\([and|or]_{j}^{s}\), whose semantic class is to be labeled, we associate the set of its syntactic-semantic _is_a_-collocates, \(H_{j}\). The elements of the set \(H_{j}\) are determined using both directions of the _is_a_ relation, as justified in the discussion above. The selection of elements of \(H_{j}\) depends on the chosen corpus \(C\) since they are extracted as collocates of \(c_{j}\) from the text of \(C\). Then, from the set \(H_{j}\), a number of most frequent collocates of \(c_{j}\) occurring in the text of \(C\) are selected as elements of \(H_{j}^{k}\). The natural number \(k\) is a parameter of the procedure, providing a potentially different graph structure for label selection. However, since we weight the label network, transferring the graph-structure properties from the underlying FoF\([and|or]^{s}\) graph onto the label graph, the most relevant nodes will emerge as the best candidates already for a reasonably low parameter \(k\), such as, e.g., \(k=15\). Using a standard collocation measure, \(f\), e.g., _logDice_ or _frequency_, we filter the \(k\) highest-ranked elements of each set \(H_{j}\), to obtain \(H_{j}^{k}\subseteq H_{j}\), the sets of \(k\) strongest _is_a_-syntactic-semantic dependency collocates of each of \(c_{j}\) in corpus \(C\). The selected lexemes that form the sets \(H_{j}^{k}\), \(j\in\{1,\ldots,n\}\), are the candidates for labels of the community FoF\([and|or]_{i}^{s}\). Namely, they will feature as nodes in the label graph constructed and analyzed in the next steps. Step (ii): We construct a label graph that incorporates the nodes of the clustered coordination community \(\text{FoF}[and|or]_{i}^{s}\) along with the strongest corresponding _is_a_ collocates obtained in the previous step. The label graph \(F[\textit{is\_a}]_{i}^{s}=G_{L}=(V_{L},E_{L})\) is then defined as a weighted directed graph.