Abstract
The problem of identifying geometric structure in heterogeneous, high-dimensional data is a cornerstone of representation learning. While there exists a large body of literature on the embeddability of graphs into specific model spaces, selecting the appropriate geometry for a given dataset remains a significant challenge. This paper introduces a fast, combinatorial method to determine the optimal geometric prior—Euclidean, Hyperbolic, or Spherical—by analyzing neighborhood growth in a regularized version of the input graph.
Introduction
In relational representation learning, the choice of embedding space significantly impacts the preservation of structural properties. While Euclidean space is the traditional default, hierarchical data often exhibits hyperbolic characteristics, and volumetric or cyclic data may be better suited for spherical geometries. Determining the "best fit" typically requires exhaustive optimization across multiple geometries and dimensions, a process that is computationally expensive and often impractical for large-scale datasets.
Methodology: The 3-Regular Score
The proposed method avoids expensive optimization by utilizing a combinatorial approach based on neighborhood growth. The process consists of two primary stages:
1. Graph Regularization
Real-world graphs often feature highly non-uniform degree distributions. To enable a consistent comparison of neighborhood growth, the author transforms the input graph $G$ into a 3-regular graph $G_3$. This transformation preserves the essential topological features of the original graph while ensuring every node has exactly three neighbors.
2. Neighborhood Growth Analysis
The core principle is that the curvature of a manifold determines the volume growth of metric balls. In discrete graphs, this corresponds to the growth rate of a node's neighborhood:
- Hyperbolic: Exponential growth (e.g., trees).
- Euclidean: Polynomial/Linear growth (e.g., lattices).
- Spherical: Sublinear growth (e.g., cycles).
The 3-regular score ($A$) aggregates these local growth patterns. A negative score indicates hyperbolic geometry, a score near zero suggests Euclidean geometry, and a positive score indicates spherical geometry.
Experimental Results
The method was validated against both synthetic models and real-world benchmark datasets. For synthetic data, the score correctly identified the geometry of canonical graphs: $N$-trees were classified as hyperbolic, lattices as Euclidean, and $N$-cycles as spherical.
In real-world benchmarks, the 3-regular score provided insights consistent with known data structures. Social networks like Facebook and the Bible wordnet were identified as highly hyperbolic. Conversely, spatial datasets such as the "Bunny" 3D mesh and geographic distances between cities were correctly classified as spherical.
Discussion and Conclusion
The 3-regular score offers a scalable, parallelizable alternative to traditional model selection methods. By relying on combinatorial counting rather than continuous optimization, it provides a rapid "pre-processing" step to identify the most promising geometric prior. While the current method focuses on the sign of the curvature rather than its precise value or the optimal dimensionality, it represents a significant step toward automated, geometry-aware representation learning.
Summary updated