Global Graph Curvature
| Autor: | Pim van der Hoorn, Egor Samosvat, Liudmila Ostroumova Prokhorenkova |
|---|---|
| Rok vydání: | 2020 |
| Předmět: |
Computer science
Graph embedding Open problem 02 engineering and technology Function (mathematics) Curvature Space (mathematics) Topology Measure (mathematics) 020204 information systems 0202 electrical engineering electronic engineering information engineering Embedding 020201 artificial intelligence & image processing Mathematics::Differential Geometry Curse of dimensionality |
| Zdroj: | Lecture Notes in Computer Science ISBN: 9783030484774 WAW |
| DOI: | 10.1007/978-3-030-48478-1_2 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|