PaperlayerView exact revision on arXiv

Source-linked AI summary

Euclidean Crowding-Driven Adaptive Euclidean-Hyperbolic Graph Learning

Hao Chen, Jian Sun, Chuan Shi, Hongying Zhang

arXiv:2610.37373v1cs.LG

TL;DR

The paper addresses limited understanding of how hyperbolic geometry benefits hierarchical graph learning and how Euclidean crowding affects learning. It analyzes layer-wise separation and margin-based generalization, then proposes EH-Fusion to adaptively combine Euclidean and hyperbolic representations. Experiments report that mixed-manifold models outperform single-manifold counterparts, with relative advantages depending on graph structure.

  • Problem

    How Euclidean crowding arises in hierarchical embeddings and affects learning performance has not been quantitatively characterized.

    Source: §I · pp. 1–2

  • Method

    The paper analyzes layer-wise Euclidean separation and its relation to margin-based generalization, and proposes EH-Fusion to adaptively balance Euclidean and hyperbolic geometry using neighborhood expansion patterns.

    Source: §I · p. 2

  • Results

    Mixed-manifold models consistently outperform their single-manifold counterparts; hyperbolic models are more effective for highly tree-like graphs, while Euclidean models grow more competitive as hyperbolicity decreases.

    Source: D. Discussion and Future Work · p. 12

  • Takeaways & Limitations

    The analysis connects layer-wise crowding to weaker margin-based guarantees, and the experiments associate geometry’s relative advantage with the graph’s intrinsic structure.

    Source: §I · p. 2, D. Discussion and Future Work · p. 12

Abstract

from arXiv · show

Hyperbolic graph representation learning has emerged as a powerful paradigm for modeling hierarchical data. Unlike Euclidean space, which exhibits polynomial volume growth, hyperbolic space grows exponentially with radius, naturally accommodating tree-like structures without the geometric distortion known as Euclidean crowding. Despite strong empirical performance, the theoretical mechanisms underlying hyperbolic embeddings remain poorly understood. In this work, we provide a geometric quantifcation research for Euclidean crowding, a generalization-theoretic explanation for the superiority of hyperbolic space on hierarchical data, and further develop an adaptive Euclidean-hyperbolic fusion learning framework toward bridging this gap. Specifically, we \textbf{first} establish a geometric quantification of Euclidean crowding by analyzing layer-wise minimum separation in node embeddings, proving that fixed-dimensional Euclidean embeddings of tree-like graphs inevitably exhibit layer-wise crowding that leads to weaker margin-based generalization bounds. \textbf{Second}, we provide a generalization-bound for the superiority of hyperbolic geometry on hierarchical data. \textbf{Third}, we propose EH-Fusion, a geometry-adaptive framework that lifts Euclidean GNN representations into hyperbolic space via exponential mapping and adaptively fuses both geometries based on node-level neighborhood expansion patterns. Extensive experiments validate our theoretical insights and demonstrate the effectiveness of EH-Fusion on benchmark datasets.

I. INTRODUCTION

Euclidean embeddings crowd nodes in deeper layers of hierarchical graphs, while hyperbolic geometry better matches tree-like expansion. The paper links this geometric difference to margin-based generalization and proposes adaptive Euclidean–hyperbolic learning for graphs with varied structures.

A. Deep Hyperbolic Representation Learning

  • Hyperbolic representations have shown strong empirical promise, but how their geometry benefits learning and how Euclidean crowding arises remain underexplored.Prior explanations emphasize global distortion or qualitative geometric intuition.Source: §I · p. 1, C. Geometric Perspective on Euclidean… · p. 3

I. INTRODUCTION

  • Fixed-dimensional Euclidean embeddings of tree-like graphs inevitably crowd nodes across layers, creating a stretch–squeeze trade-off between parent–child distances and non-adjacent-node separation.Maintaining non-adjacent separation stretches parent–child edges, whereas preserving tree-path distances compresses non-adjacent-node separation.Source: §I · pp. 1–2
  • EH-Fusion dynamically balances Euclidean and hyperbolic geometries using node-level neighborhood expansion patterns to support learning across heterogeneous graph structures.The framework addresses geometric mismatch without explicit curvature estimation and curvature-driven reconstruction.Source: §I · pp. 2–3

B. Hyperbolic Graph Representation Learning

  • Hyperbolic graph learning ranges from mapping Euclidean representations onto hyperbolic space to integrating hyperbolic operations throughout a network; this paper connects its advantage to metric geometry.The paper frames the underlying question as what drives hyperbolic representations’ effectiveness and guides pathway selection.Source: B. Hyperbolic Graph Representation… · p. 3

C. Geometric Perspective on Euclidean Crowding

  • Layer-wise minimum separation quantifies Euclidean crowding, which reduces distance-model functional margins and weakens margin-based generalization guarantees.The analysis complements global-distortion theories by examining how minimum separation decays with tree depth.Source: §I · p. 2, C. Geometric Perspective on Euclidean… · p. 4

III. PRELIMINARY

The preliminaries introduce the geometric objects and maps used to describe curved representation spaces. They identify hyperbolic space’s exponential volume growth as a reason it suits hierarchical data.

A. Riemannian Geometry

  • A Riemannian manifold equips a smooth manifold with an inner product that induces geometric quantities such as length and curvature.A tangent space at a point is the vector space of tangent vectors there, isomorphic to R^n.Source: A. Riemannian Geometry · p. 4
  • The exponential map sends a tangent vector to a point on the manifold along its geodesic, while the logarithmic map provides the inverse mapping to the tangent space.Geodesic distance is defined by the infimum of curve lengths between two points.Source: A. Riemannian Geometry · p. 4

B. Hyperbolic Manifold

  • Hyperbolic manifolds have constant negative curvature and exponential volume growth, a property suited to hierarchical data.The Poincaré ball and Lorentz model are isometric representations of hyperbolic space.Source: B. Hyperbolic Manifold · p. 4

C. Metric Space

The preliminaries define metric and tree distances, then use Gromov δ-hyperbolicity to characterize how closely a graph’s global distances resemble a tree. Smaller δ indicates stronger tree-likeness.

C. Metric Space

  • A metric space consists of points equipped with a distance function satisfying non-negativity, identity of indiscernibles, symmetry, and the triangle inequality.The Euclidean hyperball uses the Euclidean ℓ2 distance metric.Source: C. Metric Space · p. 4
  • A tree metric sums edge weights along the unique shortest path between two nodes, which passes through their lowest common ancestor.The setup assigns positive edge weights that do not increase with depth.Source: C. Metric Space · pp. 4–5

D. Gromov δ-Hyperbolicity

  • A metric space is δ-hyperbolic when the two largest of the three pairwise-distance sums for every four points differ by at most 2δ; smaller δ indicates greater tree-likeness.Trees are 0-hyperbolic, and the paper uses δ-hyperbolicity as a global structural indicator for likely benefit from hyperbolic representations.Source: D. Gromov δ-Hyperbolicity · p. 5

E. Problem Setting and Learning Objective

The section frames hierarchical graph learning as preserving parent–child structure, then shows that fixed-dimensional Euclidean embeddings face a depth-dependent separation trade-off. It links this crowding to weaker margin-based generalization guarantees.

E. Problem Setting and Learning Objective

  • Distance-based link prediction tests whether parent–child pairs are closer than non-adjacent pairs, including siblings and nodes from different branches.The graph is modeled with direct parent–child edges and node features.Source: E. Problem Setting and Learning… · p. 5

IV. GEOMETRIC CROWDING AND GENERALIZATION

  • Fixed-dimensional Euclidean embeddings of tree-like graphs inevitably crowd nodes within deeper layers, limiting separation between nodes from different branches.The analysis uses layer-wise minimum separation rather than global metric distortion.Source: §IV · p. 5, A. Euclidean Crowding in Hierarchical… · p. 6
  • Crowding reduces achievable pairwise margins and consequently weakens margin-based generalization guarantees.The framework connects the geometric separation gap between positive and negative pairs to the functional margin.Source: §IV · p. 5

A. Euclidean Crowding in Hierarchical Representations

  • When radial extent remains proportional to tree distance, Euclidean layer separation decays exponentially with depth; constant separation instead requires exponential radial stretching.The bound is δ_l ≤ C A_l k^(-l/d), exposing a stretch–squeeze trade-off.Source: A. Euclidean Crowding in Hierarchical… · p. 6

B. From Geometric Separation to Functional Margin

The analysis connects pairwise geometric separation to functional margins and derives tighter margin-based guarantees for hyperbolic metrics on tree-like data. The framework then combines Euclidean and hyperbolic representations, with node-wise fusion guided by local structure.

B. From Geometric Separation to Functional Margin

C. Margin-Based Generalization Advantage of Hyperbolic Metrics

  • For tree-like data, hyperbolic representations yield larger positive–negative separation and functional margins, producing tighter margin-based guarantees when empirical margin errors are comparable.The hyperbolic model has a smaller margin-dependent complexity term than its Euclidean counterpart.Source: C. Margin-Based Generalization… · pp. 6–7

V. FROM THEORY TO MODEL: THE EH-FUSION FRAMEWORK

  • EH-Fusion maps shared Euclidean graph representations to multiple manifolds and adaptively fuses their predictions using node-level neighborhood expansion patterns.The framework retains Euclidean graph encoders while adding lightweight geometric mappings and node-wise mixing.Source: §V · p. 7, Figure 2 · p. 7

A. Multi-Geometry Embedding via Lightweight Exponential Mapping layers

  • The embedding module keeps message passing in Euclidean space, then maps shared representations into Euclidean, Poincaré-ball, and Lorentz embeddings.The Poincaré and Lorentz representations use exponential maps; the Lorentz model is noted for stable distance computations and large-scale convenience.Source: A. Multi-Geometry Embedding via… · pp. 7–8, §V · p. 7

B. Node-wise Adaptive geometry Selection

EH-Fusion estimates local neighborhood growth and uses it to select and combine geometric predictions for each node. Rapidly expanding, tree-like regions favor hyperbolic components, while flatter regions rely more on Euclidean representations.

B. Node-wise Adaptive geometry Selection

  • Node-wise structural growth signals include i-hop neighborhood degrees, with rapid high-order growth associated with tree-like structure and slower growth with locally Euclidean geometry.The signals include diag(A^i), described as counts of length-i closed walks rooted at each node.Source: B. Node-wise Adaptive geometry Selection · p. 8
  • A lightweight attention mechanism transforms each node’s structural growth features into geometry-specific mixing weights across Euclidean, Poincaré, and Lorentz models.The weights are produced by an MLP followed by softmax normalization.Source: B. Node-wise Adaptive geometry Selection · p. 8
  • The final link probability is a convex combination of geometry-specific probabilities, allowing nodes to emphasize the geometry matching their local growth pattern.Rapidly expanding tree-like regions favor hyperbolic weights, while flatter regions rely more on Euclidean representations.Source: B. Node-wise Adaptive geometry Selection · p. 8

A. Experimental setup

The experiments span graph benchmarks with varied domains and hyperbolicity, comparing Euclidean and hyperbolic approaches under tuned settings. EH-Fusion performs strongly across graph structures and embedding dimensions.

1) Datasets:

  • The five benchmarks cover citation, transportation, disease-propagation, and product co-purchase graphs, with smaller Gromov δ indicating stronger tree-likeness.Ele-Fashion contains 97,766 nodes and 199,602 edges.Source: 1) Datasets · p. 8

2) Baselines:

  • Baselines include Euclidean GCN and GAT alongside hyperbolic Poincaré embeddings, HGCN, HNN, and FHNN.The comparison spans Euclidean and hyperbolic graph-learning approaches.Source: 2) Baselines · pp. 8–9

3) Implementation Details:

  • Hyperparameters are selected by validation performance; GNN models use early stopping after 100 epochs without validation improvement.The setup also varies learning rates, regularization, dropout, visual encoders, and dimensions 8, 16, 32, and 64.Source: 3) Implementation Details · p. 9

B. Experimental Results

  • On Disease, GAT-EH-Fusion reaches 98.1% AUC; on Airport, it reaches 97.7%, the best reported overall performance on both datasets.These strongly hyperbolic datasets have δ values of 0 and 1, respectively.Source: B. Experimental Results · p. 9, Table I · p. 10
  • EH-Fusion achieves 95.3% on Cora and 96.9% on Citeseer, remaining competitive or superior even at embedding dimensions 8, 16, and 32.The proposed models maintain stable performance across datasets with different levels of hyperbolicity.Source: B. Experimental Results · pp. 9–10
  • On Ele-Fashion, GCN2L generally outperforms Euclidean GCN across visual encoders and embedding dimensions, with improvements stable across configurations.For ImageBind features, GCN2L rises from 79.45% to 80.34% at dimension 8, from 82.43% to 83.08% at dimension 16, and from 82.46% to 83.30% at dimension 32.Source: B. Experimental Results · p. 10, Table II · p. 10

1) Ablation Study :

A single hyperbolic mapping substantially benefits strongly hierarchical graphs, while adaptive fusion stabilizes performance as graph hyperbolicity varies. The experiments also relate these effects to backbone capacity and discuss geometric measures for graph generation.

1) Ablation Study :

  • EH-Fusion reaches 98.1% on Disease with GAT and 97.7% on Airport, while Citeseer GCN recovers to 95.9% versus 92.0% under Lorentz mapping.The ablations report gains from adding a single hyperbolic mapping on strongly hyperbolic datasets and fusion gains across structural regimes.Source: 1) Ablation Study · p. 11

2) Effect of Gromov Hyperbolicity:

  • As δ decreases, Lorentz GAT AUC rises from 94.8% to 97.5%, while Euclidean GAT falls from 97.2% to 89.9%.Smaller δ denotes stronger hyperbolicity; the passage relates weaker hierarchy to reduced crowding and greater Euclidean compatibility.Source: 2) Effect of Gromov Hyperbolicity · p. 11, Figure 4 · p. 11

3) Impact of EH-Fusion for Avoiding Geometric Mismatch:

  • Fixed hyperbolic mapping gains diminish or sometimes reverse on less tree-like Cora and Citeseer, whereas EH-Fusion maintains or improves performance across datasets.The fusion mechanism emphasizes hyperbolic representations for strong hierarchy and Euclidean representations for flatter structure.Source: 3) Impact of EH-Fusion for Avoiding… · pp. 11–12, Figure 5 · p. 11

4) Impact of Backbone Model:

  • Stronger GCN and GAT backbones generally perform better with mapping or EH-Fusion, and sufficient encoder capacity can make a single hyperbolic realization effective.The discussion contrasts expressive deep encoders with typically shallow GNNs, for which additional hyperbolic operations may help.Source: 4) Impact of Backbone Model · p. 12, Figure 6 · p. 12

D. Discussion and Future Work

  • The paper links Euclidean layer-wise crowding to weaker margin-based generalization guarantees and proposes EH-Fusion to balance Euclidean and hyperbolic metrics for mixed structures.It presents structural separability and local crowding measures as potentially useful for downstream tasks.Source: D. Discussion and Future Work · p. 12
  • The discussion identifies the lack of a principled δ-hyperbolicity threshold for choosing embedding geometry and proposes separation measures for graph-generation evaluation, regularization, and conditioning.For generation, Δ-related measures could guide geometric fidelity and controllable hierarchical patterns.Source: D. Discussion and Future Work · p. 12

APPENDIX A PROOF OF THEOREM 1

In fixed, moderate Euclidean dimensions, same-layer separation decreases with depth, exposing a stretch–squeeze trade-off: preserving separation requires exponentially growing radial distances, while constraining radial growth leads to crowding.

APPENDIX A PROOF OF THEOREM 1

  • The proof bounds the layer's radial extent by accumulated edge lengths, then compares volumes using disjoint balls around its embedded nodes.This volume argument yields the layer-separation bound.Source: Appendix A · pp. 12–13
  • The bound assumes preserved radial tree distances and unchanged edge weights; increasing dimension can partly mitigate the resulting crowding.The stated condition concerns the embedding's radial distances and the tree's edge weights.Source: Appendix A · p. 14
  • At fixed, moderate dimension, same-layer minimum separation falls roughly as k^-l/d with depth, up to a polynomial factor in l.The exponent 1/d suggests that increasing embedding dimension can partly mitigate crowding.Source: Appendix A · p. 14
  • Keeping same-layer separation bounded away from zero requires exponentially growing radial distances; constraining radial growth instead leads to layer crowding.The paper describes this geometric tension as the stretch–squeeze trade-off.Source: Appendix A · p. 14

APPENDIX B PROOF OF LEMMA 1

The lemma defines functional margin on real-valued pair scores and characterizes its maximum through the separation between positive- and negative-pair distances.

APPENDIX B PROOF OF LEMMA 1

  • The functional margin is defined on real-valued pair scores s(u, v) = r − d(u, v), before sigmoid transformation.The sigmoid maps scores to (0, 1), compressing large values and distorting relative margin magnitudes.Source: Appendix B · p. 14
  • Positive pairs have distances at most d+, while negative pairs have distances at least d−, bounding their respective signed scores.The lemma combines these two cases to characterize the worst signed score.Source: Appendix B · p. 14
  • The optimal threshold balances the positive- and negative-pair terms at r⋆, maximizing the resulting piecewise-linear margin.The paper identifies the objective as a concave, piecewise-linear function of r.Source: Appendix B · p. 14
  • The geometric separation between negative and positive pairs is Δ := d− − d+.Source: Appendix B · p. 14

APPENDIX C PROOF OF THEOREM 2

For near-tree data, hyperbolic metrics admit near-isometric representations of hierarchical distances, whereas Euclidean crowding moves negative pairs closer and creates a strict margin advantage. Since larger margins can tighten margin-based generalization guarantees, the proof uses a ramp-loss surrogate to relate margins to 0–1 risk.

APPENDIX C PROOF OF THEOREM 2

  • The proof applies a ramp-loss surrogate to pairwise signed scores; it upper-bounds 0–1 loss and is 1/γ-Lipschitz.Source: Appendix C · p. 14, Figure 7 · p. 14
  • For near-tree data, hyperbolic metrics admit near-isometric representations of hierarchical distances,, while Euclidean crowding brings negative pairs progressively closer, yielding a strict margin advantage.Source: Appendix C · p. 15
  • Because the complexity penalty scales as O(1/γ), larger hyperbolic margins can lead to tighter margin-based generalization guarantees than Euclidean margins.Source: Appendix C · p. 15

Related papers

Loading 2610.37373v1…