Global graph curvature

Liudmila Prokhorenkova, Egor Samosvat, Pim van der Hoorn

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

Abstract

Recently, non-Euclidean spaces became popular for embedding structured data. However, determining suitable geometry and, in particular, curvature for a given dataset is still an open problem. In this paper, we define a notion of global graph curvature, specifically catered to the problem of embedding graphs. We theoretically analyze this value and show that the optimal curvature essentially depends on the dimensionality of the embedding space and loss function one aims to minimize via embedding. We also review existing notions of local curvature (e.g., Ollivier-Ricci curvature) and conduct a theoretical analysis of their properties. In particular, we demonstrate that the global curvature differs significantly from the aggregations of local ones. Thus, the proposed measure is non-trivial and it requires new empirical estimators as well as separate theoretical analysis.

Original languageEnglish
Title of host publicationAlgorithms and Models for the Web Graph - 17th International Workshop, WAW 2020, Proceedings
EditorsBogumil Kaminski, Przemyslaw Szufel, Pawel Pralat
PublisherSpringer
Pages16-35
Number of pages20
ISBN (Print)9783030484774
DOIs
Publication statusPublished - 2020
Event17th International Workshop on Algorithms and Models for the Web Graph, WAW 2020 - Warsaw, Poland
Duration: 21 Sep 202022 Sep 2020

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume12091 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference17th International Workshop on Algorithms and Models for the Web Graph, WAW 2020
CountryPoland
CityWarsaw
Period21/09/2022/09/20

Keywords

  • Curvature
  • Graph embedding
  • Non-Euclidean spaces

Fingerprint Dive into the research topics of 'Global graph curvature'. Together they form a unique fingerprint.

Cite this