Abstract
Selecting the appropriate geometric space—Euclidean, hyperbolic, or spherical—is critical for minimizing distortion in graph embeddings. Traditional optimization-based selection methods are computationally intensive and require pre-defined dimensionality. This paper proposes a combinatorial approach that determines the optimal geometric prior by analyzing local neighborhood growth rates. By transforming graphs into 3-regular structures, we derive a "3-regular score" that accurately predicts the intrinsic geometry of diverse datasets with linear complexity.
Introduction
In relational representation learning, mapping graph nodes into continuous geometric spaces is a standard technique for downstream tasks. While Euclidean space is the default, it often fails to capture the hierarchical nature of social networks or the cyclic structure of meshes. Hyperbolic spaces excel at representing trees, while spherical spaces are better suited for graphs with high cycle density. Currently, choosing between these geometries involves expensive "brute force" optimization. This work introduces a faster, connectivity-based alternative.
Methodology: Neighborhood Growth and Regularization
The fundamental insight is that the growth rate of a node's neighborhood reflects the underlying curvature of the space. Hyperbolic spaces exhibit exponential growth, Euclidean spaces show polynomial growth, and spherical spaces demonstrate sublinear growth due to space contraction.
However, real-world graphs have heterogeneous degree distributions that can mask these growth patterns. To address this, the paper introduces a 3-regularization step.
As shown in Figure 1, various motifs like leaves, chains, and stars are transformed into 3-regular structures while preserving essential topological properties. This "quasi-isometric embedding" ensures that neighborhood growth rates are directly comparable across different nodes and graphs. Following regularization, a 3-regular score ($A$) is calculated:
- $A < 0$ indicates Hyperbolic geometry.
- $A > 0$ indicates Spherical geometry.
- $A \approx 0$ indicates Euclidean geometry.
Experimental Validation
The method was tested on a wide range of synthetic models (Erdős-Rényi, Watts-Strogatz, Albert-Barabási) and real-world benchmarks, including wordnets (BIBLE), 3D meshes (BUNNY), and social networks (Facebook).
Results and Discussion
As illustrated in Figure 2, the 3-regular score consistently identifies the correct geometric prior. For instance, the BIBLE dataset, known for its hierarchical structure, yielded a strongly negative score (hyperbolic), while the BUNNY mesh yielded a strongly positive score (spherical).
Crucially, this method aligns with empirical results from optimization-based embedding techniques. In datasets like "Cities" and "PhD students," the space predicted by the 3-regular score matched the space that achieved the lowest average distortion ($D_{avg}$) and highest Mean Average Precision (MAP) in actual embeddings.
Conclusion
The 3-regular score provides a computationally efficient "pre-flight check" for graph embeddings. By shifting the focus from expensive optimization to local connectivity analysis, this approach enables scalable and principled selection of geometric priors for large-scale relational data.
Summary updated