In this paper, we present WebIsAGraph, a very large hypernymy graph compiled from a dataset of is-a relationships extracted from the CommonCrawl. We provide the resource together with a Neo4j plugin to enable efficient searching and querying over such large graph. We use WebIsAGraph to study the problem of detecting polysemous terms in a noisy terminological knowledge graph, thus quantifying the degree of polysemy of terms found in is-a extractions from Web text.
Acquiring concept hierarchies, i.e., taxonomies
from text, is a long-standing problem in
Natural Language Processing (NLP). Much previous
work leveraged lexico-syntactic patterns, which
can be either manually defined
Copyright c 2019 for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0).
1http://commoncrawl.org
Methods for hypernym detection like, e.g.,
pattern-based approaches, have a limitation in
that they do not necessarily produce proper
taxonomies
In this paper, we present an initial solution to these problems by building the first very large hypernymy graph, dubbed WebIsAGraph, built from is-a relationships extracted from a Web-scale corpus. This is a relevant task: although WordNet (and other thesauri) already provides a catalog of ambiguous terms, many nodes of WebIsAGraph are not covered in available lexicographic resources, because they are proper names, technical terms, or polysemantic words. Our graph – which we make freely available to the research community to foster further work on Web-scale knowledge acquisition – is built from the WebIsADb on top of state-of-the-art graph mining tools2: thanks to an accompanying plugin, it can be easily searched, queried, and explored. We2Neo4j: https://neo4j.com/ bIsAGraph may represent an opportunity to researchers for investigating approaches to a variety of tasks on large automatically acquired term tuples. As an example, we use our resource to investigate the problem of identifying ambiguous terminological nodes. To automatically detect whether a lexicographic node is ambiguous or not, we use information from both the graph (topological features) and textual labels (word embeddings) as features to train a model using supervised learning. Our results provide a first estimate of the degree of polysemy that can be found among is-a relationships from the Web. 2
We created a directed hypernymy graph from the
WebIsADb
After removing matches with a frequency lower than 3 and isolated nodes, i.e., nodes with degree equal to 0, we obtained a directed graph consisting of 33,030,457 nodes and 65,681,899 directed edges (see Table 1). The generation of such a large graph required several weeks of computation on a quad-core machine with 32 GB of RAM, using a state-of-the art graph-db system, like Neo4j. Note that the inherent sequential nature of the task of indexing tuples, nodes and edges does not benefit from the use of parallel computation. Next, we developed efficient tools for graph querying, which are released to the community, and described in https://sites.google.com/ unitelmasapienza.it/webisagraph/, where we also include examples of queries. 3
Let pSI (n) be the function that predicts if a terminological node n corresponds to a monosemous or a polysemous concept. We leverage a companion sense inventory as a ground truth, and we train different classifiers with a combination of topological WebIsAGraph nodes edges weakly connected components nodes of largest component Avg. node Degree and textual features, described hereafter. Topological features. Our conjecture is that in a taxonomy-like terminological graph (even a noisy one) there is a correlation between the mutual connectivity of a node neighborhoods and its polysemy. For example, consider the polysemous word machine – which, according to WordNet, has at least six heterogeneous meanings, ranging from the ‘any mechanical or electrical device’ to ‘a group that controls the activities of a political party’ – and the monosemous word floppy disk. We expect to observe a different degree of mutual connectivity across the corresponding incoming and outgoing nodes. In particular, for monosemous words, we expect a higher mutual connectivity. With reference to Figure 1, left side, the two hypernyms of ”floppy disk”: ”memory” and ”data storage”, have also ”RAM” as a common hyponym. In contrast, nodes in the direct neighborhood of ”machine” (leftmost graph in Figure 1) do not have mutual connections.
Our aim is thus to identify topological features that may help quantifying the previously described connectivity properties. To cope with scalability, we consider topological features built on top of 1-hop/2-hop sub-graphs of a node n. Hence, we identify two induced sub-graphs G +(n) and G+ (n), induced on V +(n) = In(n) [v2In(n) Out(v) and V + (n) = Out(n) [v2Out(n) In(v) respectively, where In(x) and Out(x) are the sets of incoming and outgoing nodes of x (including x). Next, we remove from these sub-graphs the node n, and compute the following features: ccG + (n) and ccG+ (n): the resulting number of weakly connected components; vG + (n) and vG+ (n): the resulting number of nodes; eG + (n) and eG+ (n): the resulting number of edges.
With reference to the example of Figure 1, the light gray sub-graph (a) is G +(n), the dark subdevice group memory data storage keyboard system machine
vehicle clan party
ROM
RAM
floppy
disk
abandoned
hardware
(a)
(b)
computer
ship
car
zip disk
induced sub-graphs for ”machine” and ”floppy
disk”, (a) G +(n) in gray and (b) G+ (n) in dark
gray. Dashed edges connect each n with its
hypernyms and hyponyms.
graph (b) is G+ (n), and furthermore for n =
”machine”: ccG + (n) = 2, ccG+ (n) = 2,
vG + (n) = 5, vG+ (n) = 5, eG + (n) = 3, and
eG+ (n) = 3, while for the n =”floppy disk”:
ccG + (n) = 1, ccG+ (n) = 1, vG + (n) = 4,
vG+ (n) = 2, eG + (n) = 3, and eG+ (n) = 1.
Textual features. Similarly to topological
features, our hypothesis is that textual features of the
neighborhood nodes should exhibit a lower
average similarity when n is polysemous. We extract
textual features on top of pre-trained word
embeddings, widely adopted in many NLP-related
tasks
# W (n) is the word embedding vector of n computed as follows: # W (n) =
P t2tokens(n) jtokens(n)j # we(t) where tokens(n) is the function that retrieves the set of tokens composing the word n (e.g., if n = hot dog, tokens(n) = fhot , dogg), and # we(t) is a pre-trained word embedding vector; in(n)# and
out(n): the cosine similarity between W (n) and the average word embeddings vector of incoming and outgoing nodes of n respectively; (1) # in(n) = CosSim(W (n);
# out(n) = CosSim(W (n);
P m2In(n)
P m2Out(n) # W (m) #
W (m) jIn(n)j jOut(n)j ) (2) ) (3)
Algo.
Rnd
NN t eN ABC d r o WGBC
Rnd ia NN d e pB ABC D
GBC
Rnd
a
i
d
ep NN
B
D
te[ABC
N
d
ro GBC
W
Computing features. Topological features are
efficiently extracted using the query tool
mentioned in Section 2. To compute textual features
(see Section 3) we use the Glove pre-trained word
embedding vector
By combining these two types of features (topological and textual) we obtained three different vector input representations consisting of 6 (only topological features), 303 (only textual features) and 309 (textual and topological) dimensions respectively.
Finally, we created three ”ground truth” sets of nodes in the graph for which pSI (n) is known. We selected a balanced number of monosemous and polysemous nouns, using the following sense inventories: i) WordNet (14,659 examples); ii) DBpedia (17,041 examples); iii) WordNet and DBpedia (31,701 examples).
Algorithms.
Random (Rnd): a random baseline which
randomly classifies the ambiguity of a node;
Neural Network (NN): a neural network with
Softmax activation function in the output layer
and dropout
Parameter selection. Based on the Area Under
Curve ROC (AUC) analysis
Results. We show in Table 2 the resulting precision, recall and F1 of the five systems across the ground truths datasets and for the combinations of features (see Section 3). The metrics are averaged on five classification experiments, with a random split (85% train, 10% validation and 5% test) of the ground truth sets. As shown in Table 2, NN outperforms the others ensemble methods, obtaining a F1 score around 0.70. The comparison of performances across the three combinations of features reveals that topological features are not enough to build a model for polysemy classification but can slightly boost the overall already compelling performances of word embeddings-based features.
In Table 3 we show the Person coefficient and
the distance correlation dCor4, with the aim of
analyzing how each feature correlates with the
polysemy observed in the three ground truth
dictionaries. We observed that the features with the
highest correlation with polysemy are eG+ , ccG +
and vG + (see Section 3). Additionally we
report the resulting weights of Permutation
Importance (PI) applied to the NN system with the
aim of measuring how the performance decreases
when a feature is perturbed, by shuffling its
values across training examples
The main contribution of this work is a new resource obtained by converting a large dataset of is-a (hypernymy) relations automatically extracted from the Web (such as WebIsADb) into a graph structure. This graph, along with its accompanying search tools, enables descriptive and predictive analytics of emerging properties of termino4 and dCor are indexes to estimate how two distributions are independent. logical nodes. We used here our new resource to investigate whether a node polysemy can be predicted from its topological features (i.e., connectivity patterns) and textual features (meaning representations from word embeddings). The results of this preliminary study have shown that textual features are good predictors of polysemy, while topological features appear to be weaker predictors even if they have a significant correlation with the polysemy of the related node.