Modeling Sense Structure in Word Usage Graphs with the Weighted Stochastic Block Model (2021)

Abstract: We suggest to model human-annotated Word Usage Graphs capturing fine-grained semantic proximity distinctions between word uses with a Bayesian formulation of the Weighted Stochastic Block Model, a generative model for random graphs popular in biology, physics and social sciences. By providing a probabilistic model of graded word meaning we aim to approach the slippery and yet widely used notion of word sense in a novel way. The proposed framework enables us to rigorously compare models of word senses with respect to their fit to the data. We perform extensive experiments and select the empirically most adequate model.

## introduction word usage graphs (wugs) are a relatively new model of graded word meaning in context @xcite @xcite . they represent word uses (i.e., words in context) within a weighted undirected graph, with edge weights reflecting the semantic proximity between uses. wugs may be obtained via human annotation by presenting annotators with pairs of words uses and asking them for proximity judgments. the wugs may then be clustered into sets of uses exhibiting high semantic proximity, in order to reflect traditional word sense distinctions @xcite , and to provide insight into key aspects of word meaning such as polysemy, vagueness, and lexical semantic change @xcite . we suggest to model wugs with a bayesian formulation of the weighted stochastic block model (wsbm), a generative model for random graphs popular in biology, physics and social sciences @xcite . the basic assumption of wsbms is that vertices belong to latent blocks (clusters), and that vertices in the same block are stochastically equivalent (i.e., they have edges drawn from the same distribution). fitting the model is equivalent to determining the optimal latent block structure providing a clustering of word uses. by using a bayesian probabilistic model of wug data we aim to approach graded word meaning in a rigorous scientific way: we perform model selection, i.e., different models are compared according to their fit to the data, and the model which explains the data best is chosen as most adequate representation of the semantic structure behind human-annotated word uses. if blocks are equated with word senses, this allows us to approach this slippery and yet widely used concept in a novel way. we may test long-standing hypotheses such as whether a graded model allowing sense overlap is a better model than a discrete one @xcite @xcite . as a probabilistic model, the wsbm allows to generate data from a fitted model, which is useful for simulating realistic wugs, e.g. when planning annotation studies. a fitted wsbm may also be used to predict values of unobserved edge weights, which is helpful for enhancing annotations. our contributions can be summarized as follows: ## related work our approach generally falls within the area of bayesian probabilistic modeling @xcite . more specifically, it is related to model-based graph clustering techniques, e.g., latent space models such as gaussian mixture models @xcite . these methods are common in the field of community detection @xcite . within computational linguistics our approach is most strongly related to generative probabilistic topic models, where words in documents are modeled as being drawn from a latent topic distribution @xcite . topics are often interpreted as senses @xcite . another common, yet non-probabilistic, modeling approach for word senses is to group word uses expressing similar meanings into clusters based on contextual features @xcite . as to our knowledge, only a small set of studies is concerned with the modeling of human-annotated wugs @xcite @xcite . this research line is motivated by insights from lexical semantics that word senses are no discrete objects @xcite . most important to note is the pioneering work of @xcite as the first to represent human-annotated word uses within graphs and then clustering the uses based on heuristics such as connected components and cliques. mccarthy et al. derived edge weights from human lexical substitution judgments for the respective target words and binarized them according to a threshold. this idea was recently modified and extended by @xcite . schlechtweg et al. used semantic proximity judgments to annotate edges. they applied correlation clustering @xcite in connection with a global threshold to group vertices with high edge weights and developed an efficient iterative sampling strategy for edges to reduce annotation load. however, these approaches are ad-hoc clustering methods which do not provide a probabilistic model for wugs. ## data a word usage graph @xmath0, e, w) is a weighted, undirected graph, where vertices @xmath1: identical 3: closely related 2: distantly related 1: unrelated recently, @xcite developed a large-scale multi-lingual resource of wugs. annotators were asked to judge the semantic relatedness of pairs of word uses (such as the two uses of grasp in (1) and ( 2 )) according to the scale in the uses were sampled from diachronic corpora of four languages (english, german, latin, swedish). the data was annotated in four rounds. after each round the accumulated annotations from the previous rounds wer represented in a wug, which was then clustered with correlation clustering @xcite , and then further use pairs were chosen according to heuristics aiming to compare uses to clusters to which they had not yet been compared. annotators showed high agreement, and comparable to previous studies. the final resource consists of wugs for 168 words with a total of 100,000 judgments including nouns, verbs and adjectives as well as monosemous and polysemous words. in our experiments we use the german and english subparts of the data set comprising 88 wugs. while for some wugs a clustering structure grouping vertices with high edge weights together is obvious, for others this is not the case (cf. @xcite . for example, see figure 1 showing the annotated uses for three words from @xcite . the uses of the word festspiel on the left and zersetzen on the right can be clearly partitioned into one/two main clusters, while the uses of abgesang in the middle have a less clearly clusterable structure. hence, it is unclear how many senses abgesang has and what the assignment of uses to senses should be. we approach these two questions by searching for the model which best explains the data. the block structure inferred by this model will then give us a number of blocks and an assignment of uses to blocks. ## stochastic block model the stochastic block model (sbm) @xcite is a simple generative process of random graphs based on the notion of groups of vertices. it assumes that each vertex of an observed graph g is member of a latent block (group) and that g was generated by first sampling vertices and then sampling edges between these vertices where the probability of observing an edge between two vertices is only determined by the block membership. once this process is formulated mathematically, the optimal latent block structure can be inferred from g. for this, given the partition @xmath2, where b @xmath3, b -1] is the block membership of vertex i, we define a model that generates a graph a with a probability ## model selection 5 following @xcite we select the best model according to the minimum description length principle @xcite . the description length of a graph measures the amount of information required to describe the data, if we encode it using a particular parametrization of the model being tested. this approach corresponds to an implementation of occam's razor, where the simplest model is selected, among all possibilities with the same explanatory power @xcite . ## model checking in order to validate the fitted models externally we test whether the inferred clustering corresponds to a clustering obtained with an independent algorithm. additionally, we use two internal validation criteria which test how well the structural properties of the observed graphs are recoverable from the inferred models. for this we apply two strategies: (i) posterior predictive checking @xcite and (ii) link prediction @xcite . ## conclusion we suggested to model human-annotated word usage graphs with a bayesian formulation of the weighted stochastic block model, compared several variations of the model and chose the bestfitting model in a principled way. in addition, we demonstrated how to interpret the inferred model as a model of word senses, but also that this interpretation is in no way necessary. the inferred models provide a stochastically-driven clustering and can be used to simulate realistic wugs. an analysis of the model fits illustrated that more flexible distributions for edge weights are needed to yield good fits for a range of graphs. we would like to emphasize that we do not claim that the wsbm is the best model for wugs. rather, we propose wsbms as a reasonable probabilistic model for our data that can be rigorously compared against competing models in a bayesian probabilistic framework, and potentially be neglected. in the future, we aim to test more flexible edge weight distributions and to compare wsbms to further probabilistic models, such as gaussian mixture models @xcite and latent space models @xcite . these models are interesting because they explicitly enforce the triangular property on graphs, which certain types of proximity judgments are known to obey @xcite . we also aim to explore mixed membership sbms @xcite and multi-graph models @xcite where the information from each annotator can be represented individually.