TY - GEN
T1 - Global graph curvature
AU - Prokhorenkova, Liudmila
AU - Samosvat, Egor
AU - van der Hoorn, Pim
PY - 2020
Y1 - 2020
N2 - 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.
AB - 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.
KW - Curvature
KW - Graph embedding
KW - Non-Euclidean spaces
UR - http://www.scopus.com/inward/record.url?scp=85086238037&partnerID=8YFLogxK
U2 - 10.1007/978-3-030-48478-1_2
DO - 10.1007/978-3-030-48478-1_2
M3 - Conference contribution
AN - SCOPUS:85086238037
SN - 9783030484774
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 16
EP - 35
BT - Algorithms and Models for the Web Graph - 17th International Workshop, WAW 2020, Proceedings
A2 - Kaminski, Bogumil
A2 - Szufel, Przemyslaw
A2 - Pralat, Pawel
PB - Springer
T2 - 17th International Workshop on Algorithms and Models for the Web Graph, WAW 2020
Y2 - 21 September 2020 through 22 September 2020
ER -