E mbedding W ords in N on- V ector S pace with U nsupervised G raph L earning (2020)

Abstract: It has become a de-facto standard to represent words as elements of a vector space (word2vec, GloVe). While this approach is convenient, it is unnatural for language: words form a graph with a latent hierarchical structure, and this structure has to be revealed and encoded by word embeddings. We introduce GraphGlove: unsupervised graph word representations which are learned end-to-end. In our setting, each word is a node in a weighted graph and the distance between words is the shortest path distance between the corresponding nodes. We adopt a recent method learning a representation of data in the form of a differentiable weighted graph and use it to modify the GloVe training algorithm. We show that our graph-based representations substantially outperform vector-based methods on word similarity and analogy tasks. Our analysis reveals that the structure of the learned graphs is hierarchical and similar to that of WordNet, the geometry is highly non-trivial and contains subgraphs with different local topology.

## introduction effective word representations are a key component of machine learning models for most natural language processing tasks. the most popular approach to represent a word is to map it to a low-dimensional vector @xcite @xcite . several algorithms can produce word embedding vectors with distances or dot products capturing semantic relationships between words; the vector representations can be useful for solving numerous nlp tasks such as word analogy @xcite , hypernymy detec-tion @xcite or serving as features for supervised learning problems. while representing words as vectors may be convenient, it is unnatural for language: words form a graph with a hierarchical structure @xcite that has to be revealed and encoded by unsupervised learned word embeddings. a possible step towards this can be made by choosing a vector space more similar to the structure of the data: for example, a space with hyperbolic geometry @xcite instead of commonly used euclidean @xcite @xcite was shown beneficial for several tasks. however, learning data structure by choosing an appropriate vector space is likely to be neither optimal nor generalizable: @xcite argue that not only are different data better modelled by different spaces, but even for the same dataset the preferable type of space may vary across its parts. it means that the quality of the representations obtained from vector-based embeddings is determined by how well the geometry of the embedding space matches the structure of the data. therefore, (1) any vectorbased word embeddings inherit limitations imposed by the structure of the chosen vector space; (2) the vector space geometry greatly influences the properties of the learned embeddings; (3) these properties may be the ones of a space geometry and not the ones of a language. in this work, we propose to embed words into a graph, which is more natural for language. in our setting, each word is a node in a weighted undirected graph and the distance between words is the shortest path distance between the corresponding nodes; note that any finite metric space can be represented in such a manner. we adopt a recently introduced method which learns a representation of data as a weighted graph @xcite and use it to modify the glove algorithm for unsuper-vised word embeddings @xcite . the former enables simple end-to-end training by gradient descent, the latter -learning a graph in an unsupervised manner. using the fixed training regime of glove, we vary the choice of a distance: the graph distance we introduced, as well as the ones defined by vector spaces: euclidean @xcite and hyperbolic @xcite . this allows for a fair comparison of vector-based and graph-based approaches and analysis of limitations of vector spaces. in addition to improvements on a wide range of word similarity and analogy tasks, analysis of the structure of the learned graphs suggests that graph-based word representations can potentially be used as a tool for language analysis. our key contributions are as follows: ## graph word embeddings for a vocabulary @xmath0, v 1 , . . . , v n }, we define graph word embeddings as an undirected weighted graph g(v, e, w). in this graph, when embedding words as vectors, the distance between words is defined as the distance between their vectors; the distance function is inherited from the chosen vector space (usually euclidean). for graph word embeddings, the distance between words is defined as the shortest path distance between the corresponding nodes of the graph: to learn graph word embeddings, we use a recently introduced method for learning a representation of data in a form of a weighted graph @xcite and modify the training procedure of glove @xcite for learning unsupervised word embeddings. we give necessary background in section 2.1 and introduce our method, graphglove, in section 2.2. ## experiments in the main text, we report results for 50k vocabulary with 20 parameters per token. results for other settings, as well as the standard deviations, can be found in the supplementary material. ## learned graph structure in this section, we analyze the graph structure learned by our method and reveal its differences from the structure of vector-based embeddings. ## related work word embedding methods typically represent words as vectors in a low-dimensional space; usually, the vector space is euclidean @xcite @xcite , but recently other spaces, e.g. hyperbolic, have been explored @xcite @xcite . however, vectorial embeddings can have undesired properties: e.g., in dot product spaces certain words cannot be assigned high probability regardless of their context @xcite . a conceptually different approach is to model words as probability density functions @xcite @xcite @xcite . we propose a new setting: embedding words as nodes in a weighted graph. representing language data in the form of a graph has been a long-standing task @xcite @xcite @xcite . graph lexicons were used to learn word embeddings specialized towards certain types of lexical knowledge @xcite @xcite @xcite . it is also possible to incorporate external linguistic information from graphs, e.g. dependency parser outputs @xcite . to learn a weighted graph, we use the method by @xcite . prior approaches to learning graphs from data are eigher highly problemspecific and not scalable @xcite ; @xcite ; @xcite or solve a less general but important case of learning directed acyclic graphs @xcite . the opposite to learning a graph from data is the task of embedding nodes in a given graph to reflect graph distances and/or other properties; see @xcite for a thorough survey. analysis of word embeddings and the structure of the learned feature space often reveals interesting language properties and is an important research direction @xcite @xcite @xcite . we show that graph-based embeddings can be a powerful tool for language analysis. ## conclusions we introduce graphglove -graph word embeddings, where each word is a node in a weighted graph and the distance between words is the shortest path distance between the corresponding nodes. the graph is learned end-to-end in an unsupervised manner. we show that graphglove substantially outperforms both euclidean and poincaré glove on word similarity and word analogy tasks. our analysis reveals that the structure of the learned graphs is hierarchical and similar to that of word-net; the geometry is highly non-trivial and contains subgraphs with different local topology. possible directions for future work include using graphglove for unsupervised hypernymy detection, analyzing undesirable word associations, comparing learned graph topologies for different languages, and downstream applications such as sequence classification. also, given the recent success of models such as elmo and bert, it would be interesting to explore extensions of graphglove to the class of contextualized embeddings.