Model-independent embedding of directed networks into Euclidean and hyperbolic spaces

The study of complex systems through networks has revealed ubiquitous features such as small-world behavior, high clustering, scale-free degree distributions, and community structure. Hyperbolic network models capture these properties by placing nodes in hyperbolic space and connecting them with probabilities that decay with hyperbolic distance, which has motivated extensive efforts to uncover hidden geometric spaces underlying real networks. Hyperbolic embeddings aim to find node coordinates that reflect observed topology. Most existing embedding methods focus on undirected networks, whereas many real systems are directed, encoding asymmetric relations and flows. Ignoring directions can lose critical information about node roles (sources vs targets) and directed community structure. The research question addressed is how to embed directed networks into Euclidean and hyperbolic spaces in a model-independent way that preserves directed topology, enabling accurate distance representation, reconstruction, and navigability while remaining applicable across network types and dimensions.

Prior hyperbolic embedding approaches include likelihood optimization based on generative models (e.g., HyperMap with E-PSO), spectral and distance-based dimension reduction (LaBNE using Laplacian; coalescent embeddings using graph distances with PSO-based radial conversion; hydra recovering hyperbolic distances via the hyperboloid model and mapping to Poincaré), and hybrids that combine dimension reduction with angular optimization under specific models (E-PSO, S1/H2). Neural network methods learn low-dimensional representations, sometimes incorporating attributes, but are harder to interpret. For directed graphs, few methods exist: asymmetric likelihood optimization in a directed S1/H2 framework and hyperbolic Gaussian embeddings where directionality emerges via KL divergence between distributions. Overall, there is a gap in general, model-independent methods that handle directed edges while providing hyperbolic coordinates in arbitrary dimensions.

Framework overview: The authors propose deterministic methods that assign separate source and target coordinates to each node to capture directionality. Two pathways are developed: (1) obtain a Euclidean embedding via dimension reduction of a proximity matrix, then convert to hyperbolic coordinates with a model-independent conversion (MIC); (2) embed directly into hyperbolic space via dimension reduction of a Lorentz product matrix derived from distances.

Euclidean embeddings via proximities (source/target):

• Construct a proximity matrix P capturing directed topology. Two options are used:
  • HOPE: Katz proximity, where P_st sums weighted counts of all paths from s to t with decay α.
  • TREXPEN: exponential shortest-path proximity P_st = exp(−q · SPL_st), where SPL_st is directed shortest path length and q>0 controls decay. For unreachable pairs, P_st=0, allowing embedding of weakly connected components.
• Variants to improve angular spread and relational focus:
  • Shifted versions (HOPE-S, TREXPEN-S): center P by subtracting its mean to allow negative values and broaden angular range.
  • Reduced versions (HOPE-R, TREXPEN-R): discard the first component from SVD and use components 2..(d+1), focusing on relative positions and often yielding circular layouts.
• Dimension reduction: perform SVD P = U Σ V^T. Source coordinates S = U Σ and target coordinates T = V Σ; for undirected graphs U=V so S=T. Optionally shift the center of mass (COM) of coordinates to the origin before conversion.

Model-independent Euclidean-to-hyperbolic conversion (MIC):

• Hyperbolic space: native representation of d-dimensional space with curvature K = −γ^2; hyperbolic distance between source s and target t is approximated by x ≈ ln(θ/2) · sqrt(r_source^2 + r_target^2), showing that smaller radii and smaller angular distances increase connection likelihood.
• Euclidean embeddings represent high proximity via large inner products r_source · r_target · cos θ, favoring large radii and small angles. MIC preserves angular coordinates and converts Euclidean radial coordinates to hyperbolic ones by matching radial attractivity across spaces.
• The conversion maps Euclidean and hyperbolic radial coordinates to a common half-line via volumes, equating normalized positions to preserve relative attractivity. With a chosen maximum hyperbolic radius r_max^hyp = C ln N (C≈2), the hyperbolic radial coordinate is set by: r_i^hyp(r_i^Euc) = (1/(d−1)) · ln(1 + [N^{C(d−1)} − 1] · (r_i^Euc / r_min^Euc)^d).
• After converting radii and keeping angles, positions are placed in the native ball of curvature K = −γ^2. Parameters: d (dimensions), γ (curvature scale, typically 1), C (extent, typically 2). Nodes with zero out-degree (for source positions) or zero in-degree (for target positions) are removed.

Direct hyperbolic embedding (TREXPIC):

• Build a directed distance matrix D with entries estimating hyperbolic distances from s to t; authors use D_st = exp(q · SPL_st) with q>0 to ensure finite values even in weak components.
• Convert to a Lorentz product matrix L with L_st = cosh(D_st).
• Perform SVD L = U Σ V^T and recover node coordinates in the hyperboloid model (dimension d+1) scaled by curvature parameter γ. Map to native ball coordinates by normalizing spatial components and setting radial coordinates via acosh of the time-like component. Produce separate source (from S=U, Σ) and target (from T=V, Σ) embeddings. Remove nodes with zero out-/in-degree for source/target.

Evaluation setup:

• Datasets: directed Wikipedia norm subnetwork (N=505, E=2081), yeast transcriptional regulation (N=662, E=1063), U.S. political blogs (N=1222, E=19,021), USF word association (N=4865, E=41,964). Only the largest weakly connected component embedded; edge weights ignored (set to 1) in main experiments. Nodes with zero out- or in-degree are not embedded in the respective role.
• Parameters: tested d ∈ {2,3,4,8,...,2^n} with d ≤ N/10. For HOPE, α sampled from a range based on adjacency spectral radius; for TREXPEN variants, q sampled from [−ln(0.9)/SPL_max, −ln(10^−50)/SPL_max]; for TREXPIC, q from [ln(1/0.9999)/SPL_max, ln(10)/SPL_max]. Curvature K set to −1; MIC used C=2. Methods are deterministic. For large networks and metrics requiring pair enumeration, random sampling up to 500,000 pairs was used.

Quality measures:

• Mapping accuracy: Spearman correlation between directed SPL and geometric measures (Euclidean distance, −inner product; hyperbolic distance) over pairs with finite SPL.
• Graph reconstruction: rank source-target pairs by geometric measures; evaluate precision at E (or sampled E), AUPR, and AUROC. Baselines include local heuristics: common neighbours (directed two-hop paths), preferential attachment (out-degree(s) × in-degree(t)), and three directed resource allocation variants.
• Greedy routing: route from s to t by choosing the neighbor minimizing geometric distance to t (Euclidean distance, −inner product, or hyperbolic distance). Report GR-score, success rate, and mean hop-length of successful routes. For large graphs, evaluate on 5 samples of 500,000 reachable pairs.

• Demonstrations on synthetic SBM networks show clear angular separation of communities in both Euclidean and hyperbolic 2D embeddings; directed source/target planes reveal link directions.
• Mapping accuracy: TREXPEN variants and TREXPIC generally achieve higher correlations between SPL and geometric measures than HOPE variants, consistent with focusing on shortest paths rather than all paths. Overall, Euclidean embeddings often yield the highest mapping accuracy, but hyperbolic embeddings are close and typically outperform Euclidean when comparing distances (rather than inner products).
• Graph reconstruction: Across Wikipedia, yeast, political blogs, and word association networks, both Katz-based (HOPE) and exponential-based (TREXPEN/TREXPIC) embeddings are effective. Generally, Euclidean inner product is a strong predictor; in the political blogs network, hyperbolic embeddings in 2D achieve the best AUPR. For distance-based ranking, hyperbolic embeddings clearly outperform Euclidean, which often struggle against simple local heuristics.
• Greedy routing: Hyperbolic embeddings achieve the highest GR-scores, with strong success rates and short path lengths; Euclidean distance-based routing is often competitive but inferior, while inner product performs poorly. Methods using exponential proximities/distances (TREXPEN, TREXPIC) consistently outperform HOPE/Katz in navigability.
• MIC conversion: Successfully maps circular Euclidean embeddings (e.g., HOPE-R, TREXPEN-R) to hyperbolic layouts that return hubs to central, radially attractive positions and preserve angular structure. MIC can outperform PSO-based radial transformations even on PSO-generated networks.
• Practical notes: Shifting the Euclidean COM often harms Euclidean embeddings but improves subsequent hyperbolic MIC results; all methods are deterministic and scale to multiple dimensions.

The proposed framework addresses the challenge of model-independent, directed network embedding by assigning source and target coordinates and leveraging dimension reduction of proximities or distances. By aligning Euclidean inner-product structure with hyperbolic distance through MIC, the methods reconcile differing radial attractivity principles and preserve angular information, yielding directed hyperbolic layouts without assuming a specific generative model. Empirical evaluations show that focusing on shortest-path information (TREXPEN/TREXPIC) enhances correspondence with topological distances, improves reconstruction, and substantially boosts navigability versus Katz-based baselines. The hyperbolic distance emerges as a versatile geometric measure that performs well across mapping accuracy, reconstruction, and routing, underscoring the suitability of hyperbolic geometry for representing directed complex networks. Visualizations in 2D benefit from hyperbolic radial separation (central hubs, peripheral low-attractivity nodes), and the methods flexibly extend to higher dimensions for improved fidelity.

This work introduces a general, deterministic framework for embedding directed networks in Euclidean and hyperbolic spaces of arbitrary dimension. Contributions include: (i) TREXPEN, a Euclidean embedding based on exponential shortest-path proximities with source/target representations; (ii) MIC, a model-independent conversion mapping Euclidean radial coordinates to hyperbolic radii while preserving angular positions; and (iii) TREXPIC, a direct hyperbolic embedding via Lorentz product recovery from exponential distance matrices. Across diverse real networks, the methods produce high-quality embeddings, with hyperbolic layouts excelling in navigability and competitive in mapping accuracy and reconstruction. The framework is broadly applicable, model-independent, and accommodates directed and weakly connected graphs. Future investigations may explore optimal parameter selection, curvature tuning, principled dimension choice, integration of weights and attributes, and probing links between network properties and underlying geometric dimensionality.

• Parameter optimization was not exhaustive; results may vary slightly with improved tuning of α or q and curvature parameters.
• Nodes with zero out-degree or in-degree cannot be represented in the corresponding source or target embedding; only the largest weakly connected component was embedded.
• For computational reasons, evaluations on larger networks used sampled node pairs, introducing variance (though reported as small).
• Euclidean edge weights were ignored in main tests (weights addressed separately in supplementary material).
• TREXPIC’s radial coordinates can show limited visual spread in 2D despite competitive quantitative performance.
• Curvature was fixed (K = −1) and MIC used a fixed extent parameter (C=2); alternative choices may affect performance and were explored only in supplementary analyses.