Hyperbolic geometry improves graph dimensions with flexible ball sizes
Hyperbolic Sphericity
Computational Geometry
Summary
Graphs can be represented by overlapping balls in space, and the smallest space dimension needed is called sphericity. This paper studies this concept not in usual flat (Euclidean) space, but in hyperbolic space—a curved geometry. The authors found that by choosing ball sizes depending on the graph, the dimension needed in hyperbolic space never exceeds that needed in flat space and can be much smaller. Fixing the ball size changes this relationship slightly but predictably. They also show that increasing the ball size can lower the needed dimension, and some graphs’ minimal dimension changes back and forth as ball size varies.
What this means in practice
- •For machine learning engineers: Design low-dimensional hyperbolic embeddings of graphs to improve efficiency and representation quality in symbolic data tasks.
- •For network analysts: Use hyperbolic ball intersection models with adjustable sizes to better capture network structures in fewer dimensions.
A theory result. No direct application yet.
Authors
Thomas Bläsius, Lennart Großkreutz, Jean-Pierre von der Heydt
Abstract
The sphericity of a graph is the minimum dimension d such that the graph has an intersection representation of d-dimensional balls of equal radius. While sphericity has been studied in Euclidean space, we initiate the study of hyperbolic sphericity. The hyperbolic sphericity of a graph can be significantly smaller than its Euclidean counterpart, but, contrary to the Euclidean setting, depends strongly on the radius of the balls. We show that, if the radius of the balls can be chosen depending on the graph, the hyperbolic sphericity is upper bounded by the Euclidean sphericity. This extends a previous result for 2-dimensional hyperbolic space, i.e., uniform disk graphs, to arbitrary dimensions. Moreover, our proof is significantly simpler. If we fix the radius, i.e., do not make it dependent on the graph, we show that hyperbolic sphericity can be larger than Euclidean sphericity, but by at most 1. Additionally, we study how hyperbolic sphericity changes with the ball radius. We show that choosing a larger radius can substantially decrease the sphericity while increasing it by at most 1. We also provide a construction of a graph where the sphericity oscillates between different values as the radius increases. Besides being theoretically interesting, we note that these results are relevant for graph embeddings in machine learning, where one is interested in low-dimensional numeric representations of symbolic data like graphs.