Making Fast Graph-based Algorithms with Graph Metric Embeddings

Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics, pages 3349–3355 Florence, Italy, July 28 - August 2, 2019. c⃝2019 Association for Computational Linguistics 3349 Making Fast Graph-based Algorithms with Graph Metric Embeddings Andrey Kutuzov†, Mohammad Dorgham‡, Oleksiy Oliynyk‡, Chris Biemann‡, and Alexander Panchenko⋆, ‡ †Language Technology Group, University of Oslo, Oslo, Norway ‡Language Technology Group, Universit¨at Hamburg, Hamburg, Germany ⋆Skolkovo Institute of Science and Technology, Moscow, Russia Abstract The computation of distance measures be- tween nodes in graphs is inefficient and does not scale to large graphs. We explore dense vector representations as an effective way to approximate the same information: we intro- duce a simple yet efficient and effective ap- proach for learning graph embeddings. In- stead of directly operating on the graph struc- ture, our method takes structural measures of pairwise node similarities into account and learns dense node representations reflecting user-defined graph distance measures, such as e.g. the shortest path distance or distance measures that take information beyond the graph structure into account. We demon- strate a speed-up of several orders of magni- tude when predicting word similarity by vector operations on our embeddings as opposed to directly computing the respective path-based measures, while outperforming various other graph embeddings on semantic similarity and word sense disambiguation tasks and show evaluations on the WordNet graph and two knowledge base graphs. When operating on large graphs, such as trans- portation networks, social networks, or lexical re- sources, the need for estimating similarities be- tween nodes arises. For many domain-specific applications, custom graph node similarity mea- sures sim : V × V → R have been defined on pairs of nodes V of a graph G = (V, E). Exam- ples include travel time, communities, or seman- tic distances for knowledge-based word sense dis- ambiguation on WordNet (Miller, 1995). For in- stance, the similarity sij between the cup.n.01 and mug.n.01 synsets in the WordNet is 1 4 according to the inverted shortest path distance as these two nodes are connected by the undirected path cup → container ← vessel ← drinking vessel ← mug. In recent years, a large variety of such node similarity measures have been described, many of which are based on the notion of a random walk (Fouss et al., 2007; Pilehvar and Navigli, 2015; Lebichot et al., 2018). As given by the structure of the problem, most such measures are defined as traversals of edges E of the graph, which makes their computation prohibitively inefficient. To this end, we propose the path2vec model1, which solves this problem by decoupling devel- opment and use of graph-based measures, and – in contrast to purely walk-based embeddings – is trainable to reflect custom node similarity mea- sures. We represent nodes in a graph with dense embeddings that are good in approximating such custom, e.g. application-specific, pairwise node similarity measures. Similarity computations in a vector space are several orders of magnitude faster than computations directly operating on the graph. First, effectiveness of our model is shown …

Content truncated to 500 words