Making fast graph-based algorithms with graph metric embeddings

Andrey Kutuzov, Mohammad Dorgham, Oleksiy Oliynyk, Chris Biemann, Alexander Panchenko

    Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

    Abstract

    The computation of distance measures between 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 introduce a simple yet efficient and effective approach for learning graph embeddings. Instead of directly operating on the graph structure, 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 demonstrate a speed-up of several orders of magnitude 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.

    Original languageEnglish
    Title of host publicationACL 2019 - 57th Annual Meeting of the Association for Computational Linguistics, Proceedings of the Conference
    PublisherAssociation for Computational Linguistics (ACL)
    Pages3349-3355
    Number of pages7
    ISBN (Electronic)9781950737482
    Publication statusPublished - 2020
    Event57th Annual Meeting of the Association for Computational Linguistics, ACL 2019 - Florence, Italy
    Duration: 28 Jul 20192 Aug 2019

    Publication series

    NameACL 2019 - 57th Annual Meeting of the Association for Computational Linguistics, Proceedings of the Conference

    Conference

    Conference57th Annual Meeting of the Association for Computational Linguistics, ACL 2019
    Country/TerritoryItaly
    CityFlorence
    Period28/07/192/08/19

    Fingerprint

    Dive into the research topics of 'Making fast graph-based algorithms with graph metric embeddings'. Together they form a unique fingerprint.

    Cite this