PaperlayerView exact revision on arXiv

Source-linked AI summary

Hyperbolic Sphericity

Thomas Bläsius, Lennart Großkreutz, Jean-Pierre von der Heydt

arXiv:2610.01336v1cs.CG

TL;DR

The paper studies graph representations in hyperbolic space, where ball radius affects which structures can be represented, and introduces hyperbolic sphericity as a dimension measure. It compares that measure with Euclidean sphericity and examines how it changes with radius, including a construction with radius-varying dimension.

  • Problem

    Unlike Euclidean sphericity, hyperbolic sphericity depends strongly on ball radius, raising questions about how the two dimensions compare and how the radius changes the required dimension.

    Source: §1 · p. 2

  • Method

    The paper defines hyperbolic sphericity for equal-sized-ball intersection representations and studies its comparison with Euclidean sphericity and its behavior across radii.

    Source: §1 · pp. 2–3

  • Results

    For every graph and radius, hyperbolic sphericity exceeds Euclidean sphericity by at most 1, and a constructed graph has radius-varying sphericity.

    Source: §1 · p. 3, §4 · p. 12

  • Takeaways & Limitations

    These dimension and radius questions are relevant to graph embeddings used as numeric representations of symbolic data in machine learning.

    Source: §1 · pp. 1–2

    It remains open whether a lower bound on a sufficiently large radius, depending only on graph size, guarantees hyperbolic sphericity within 1 of its minimum.

    Source: §5 · p. 20

Abstract

from arXiv · show

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.

1 Introduction

The introduction defines hyperbolic sphericity to study graph representations in hyperbolic space, where unlike Euclidean space the ball radius affects representability. It frames comparisons with Euclidean sphericity and radius-dependent behavior as central questions, then situates them among graph-embedding applications and related work.

1 Introduction

  • Graph embeddings provide numeric representations of symbolic data for machine-learning tasks including link prediction, node classification, and community detection [22,45,51].Low-dimensional representations are also valuable for visualization and computational efficiency, while inaccurate representations can mislead.Source: §1 · p. 1
  • Hyperbolic space expands exponentially, providing room to separate nonadjacent vertices near a common center; stars and arbitrary trees can be represented as 2D hyperbolic disk graphs [49].By contrast, Euclidean stars can require sphericity at least Ω(log n).Source: §1 · p. 2
  • Hyperbolic sphericity is the minimum dimension for representing a graph as an intersection graph of equally sized hyperbolic balls, and the ball radius affects which structures are representable.In Euclidean space, uniform scaling makes the radius irrelevant; in hyperbolic space it does not.Source: §1 · p. 2
  • For every graph and radius, hyperbolic sphericity exceeds Euclidean sphericity by at most 1; the paper also studies sufficiently small radii and gives a simpler arbitrary-dimensional proof extending prior 2D work [10].Larger radii exceed the minimum hyperbolic sphericity by at most 1, and the paper constructs a graph whose sphericity oscillates with radius.Source: §1 · p. 3

1.1 Related Work

  • Prior work on higher-dimensional hyperbolic ball graphs is limited, while studies of 2D hyperbolic disk graphs examine structural and algorithmic properties [10,14,27].Related work also covers hyperbolic random graphs and graph drawing, and distinguishes intersection representations from planar straight-line drawings [18].Source: §1.1 · pp. 3–4

1.2 Outline

  • The paper develops hyperbolic geometry and sphericity preliminaries, compares Euclidean and hyperbolic sphericity in Section 3, and constructs a graph with oscillating hyperbolic sphericity in Section 4.The construction uses results on maximum-area k-gons and constrained hyperbolic quadrilaterals before the paper closes with open questions.Source: §1.2 · p. 5

2 Preliminaries

The preliminaries establish the hyperbolic models and define Euclidean and hyperbolic sphericity, emphasizing that hyperbolic representations depend on radius. They also provide geometric lemmas used in the later graph construction.

2 Preliminaries

  • In the upper half-space model, hyperbolic geodesics are open rays or semicircles orthogonal to the boundary, and the model is conformal.In the Poincaré disk, geodesics are circular arcs meeting the boundary orthogonally; hyperbolic circles appear as Euclidean circles with different centers and radii.Source: §2 · pp. 5–6
  • The preliminaries state that triangle area equals π minus the sum of its interior angles, and illustrate a 2D hyperbolic representation of a binary tree.The binary-tree illustration uses a {3, ∞}-tiling that permits recursive construction.Source: §2 · p. 6, Figure 2 · p. 6
  • Euclidean sphericity is the minimum dimension admitting an equal-radius ball intersection representation, whereas hyperbolic sphericity is defined both at radius s and as the minimum over radii.The Euclidean choice of radius is immaterial, but hyperbolic sphericity with fixed radius can vary.Source: §2 · p. 6
  • If two edge-geodesic segments cross in a 2D hyperbolic uniform ball graph representation, their four endpoints induce at least one triangle.The proof bounds two of the endpoint distances by 2s using the intersection point and the triangle inequality.Source: §2 · p. 7
  • For a triangle with a,b ≤ x and c > x, sin(γ/2) > sinh(x/2)/sinh(x); when a,b > x and c ≤ x, the inequality reverses.The first bound follows by reducing to an isosceles triangle; the second uses the hyperbolic law of cosines and monotonicity.Source: §2 · pp. 7–8

3 Relation Between Hyperbolic and Euclidean Sphericity

Hyperbolic sphericity depends on ball radius, but the paper bounds its relation to Euclidean sphericity across radius choices. A sufficiently small radius needs no more dimensions than the Euclidean optimum; arbitrary and sufficiently large radii incur at most a one-dimension increase under the stated comparisons.

Relation Between Hyperbolic and Euclidean Sphericity

  • At sufficiently small radii HSphs(G) ≤ ESph(G); at any radius it is at most ESph(G)+1, and sufficiently large radii cost at most one dimension over HSph(G).Source: §3 · pp. 8–10

Small Radius

  • Shifting a finite point set sufficiently far upward preserves the ordering of Euclidean and hyperbolic pair distances, enabling a same-dimension hyperbolic representation at sufficiently small radii.The construction translates an EUBG representation into upper half-space and chooses a radius separating edge from non-edge distances.Source: §3 · pp. 8–9
  • Small-radius hyperbolic sphericity need not equal Euclidean sphericity: the six-leaf star has values 2 and 3, respectively.Source: §3 · p. 9

Arbitrary Radius

  • For any fixed hyperbolic radius, a d-dimensional Euclidean representation converts to a (d+1)-dimensional hyperbolic one, making the +1 bound constructive.The construction embeds the Euclidean representation in one additional dimension and selects coordinates to realize the desired hyperbolic radius.Source: §3 · p. 10
  • Increasing the radius from s1 to s2 can map a d-dimensional hyperbolic representation into d+1 dimensions while preserving adjacency.The mapping preserves Euclidean pair distances and adjusts the hyperbolic distance cutoff.Source: §3 · pp. 10–11

4 Graph with Non-Monotonic Hyperbolic Sphericity

This section constructs a graph whose hyperbolic sphericity is 2 at two radii and exactly 3 throughout an interval between them. Geometric results on polygons and quadrilaterals, including angle bounds, establish this non-monotonicity and guide construction of a valid drawing by adjusting vertex placement.

4 Graph with Non-Monotonic Hyperbolic Sphericity

  • A cycle of 8 vertices with 33 attached length-2 paths has 2-dimensional representations at small and large radii, but not at an intermediate radius.At small radii one path fits inside the cycle and the other 32 fit around it; at large radii all paths fit outside.Source: §4 · p. 11

4.1 Area Maximum k-Gons

  • Among hyperbolic k-gons whose sides are at most x, the maximum-area polygon is regular with every side equal to x.The lemma also gives a formula for the internal angles of this polygon.Source: §4.1 · p. 12

4.2 Quadrilateral with Minimal Angle Sum

  • Angle-sum minima occur in two configurations: all four sides have length x, or three sides and one diagonal have length x.In the second configuration, the angle sum decreases with angle D when cosh(x) ≤ 2, but has a unique minimum when cosh(x) > 2.Source: §4.2 · pp. 14, 18

4.3 Putting Things Together

  • HSph_s(C~)=3 throughout [0.765, 0.770], but equals 2 at s1=0.7635 and s2=0.7795.In that interval, planar representations require each attached path to lie inside or outside the cycle, but neither placement works.Source: §4.3 · pp. 18–19
  • The argument groups consecutive-neighbor angles into three types and lower-bounds their total, which cannot exceed 2πk in a valid representation.Type 1 angles are at least A=2 asin(sinh(s)/sinh(2s)); paired type 2 angles contribute B=min(f1(2s),f2(2s)), while type 3 angles are minimized when the k-gon is regular.Source: §4.3 · p. 19
  • For s ∈ [0.765, 0.770], the hyperbolic sphericity of ˜C is exactly 3, with su=0.770, k=8, p=33, and S≈50.290>2πk≈50.265.The angle-sum bound gives the lower bound, and Theorem 7 supplies the matching upper bound.Source: §4.3 · p. 20
  • A valid hand-drawn HUBG representation can be obtained by placing vertices on a regular {3, 8}-tiling and rotating the outer path-vertex layer to reduce type 3 angles.The initial arrangement has touching balls for some unconnected vertices; rotation creates slack to decrease the radius and obtain a valid representation.Source: §4.3 · p. 20

5 Open Problems

The open problems ask how large hyperbolic sphericity can grow, how radius thresholds and Euclidean–hyperbolic gaps scale, and whether radius-dependent oscillations can occur arbitrarily often. The proposed oscillation construction yields separated radius intervals for individual graphs, but combining them into one graph remains unresolved.

Growth of hyperbolic sphericity

  • Whether hyperbolic sphericity can grow linearly with graph size remains open; for K_n,n, the Euclidean and dot-product lower bound is n, while the hyperbolic lower bound is logarithmic.The best known lower bound for non-uniform ball graphs is also logarithmic, and applies to hyperbolic unit ball graphs.Source: §5 · p. 20

Radius threshold

  • A graph-size-dependent radius threshold s* guaranteeing hyperbolic sphericity within 1 of its minimum is open; stars may require the largest threshold, growing logarithmically with graph size.This question was already stated in [4].Source: §5 · p. 20

Euclidean–hyperbolic gap

  • It remains unclear whether stars’ logarithmic gap between Euclidean and hyperbolic sphericity is the largest possible asymptotic difference.For stars, an EUBG representation requires at most logarithmically more dimensions than a HUBG representation.Source: §5 · p. 20

Oscillation with radius

  • The authors conjecture that a family of graphs can make hyperbolic sphericity oscillate arbitrarily often between two values as radius increases, using disjoint unions of variants of ˜C.The challenge is ensuring that one graph’s invalid radius regions do not overlap too much with another’s valid regions.Source: §5 · pp. 20–21
  • For each constructed graph ˜C(k), the bounds identify a radius interval requiring at least 3 dimensions, and the intervals for successive k values do not overlap.Figure 10 plots the interval sizes and distances between intervals; constructing one graph with arbitrarily many oscillations still requires controlling overlap between invalid and valid regions.Source: §5 · pp. 20–21, Figure 10 · p. 21
Loading 2610.01336v1…