Introduction
Directed graphs (digraphs) represent complex systems where relationships are inherently directional, such as citation networks, web links, and social media flows. Traditional Graph Neural Networks (GNNs) often struggle with digraphs because they either symmetrize the adjacency matrix or fail to capture the nuanced semantics of directed connectivity. This paper introduces D-HYPR (Digraph HYPERbolic Networks), a framework that leverages hyperbolic geometry and multi-faceted neighborhood modeling to address these limitations.
Methodology
D-HYPR addresses two primary challenges in digraph representation learning through three key innovations:
- Hyperbolic Embedding Space: Instead of standard Euclidean space, D-HYPR utilizes the Poincaré ball model of hyperbolic geometry. Hyperbolic space expands exponentially, making it a natural fit for the hierarchical and power-law structures found in real-world digraphs. This allows the model to maintain high accuracy even in low-dimensional settings.
- Neighborhood Collaborative Learning: Standard GNNs typically focus on direct neighbors (diffusion). D-HYPR expands this by defining four types of $k$-order proximity: Diffusion In/Out and Common In/Out (nodes sharing a common parent or child). As shown in Figure 1, "common" neighborhoods often provide a significantly larger and more semantically rich receptive field than simple diffusion paths.
- Asymmetry-Preserving Regularizers: To handle directionality, the model uses a gravity-inspired decoder that learns a "mass" for each node. This models preferential attachment—the idea that some nodes are "hubs" or "authorities"—preserving the asymmetric influence between nodes.
Experimental Setup
The researchers evaluated D-HYPR on eight real-world digraph datasets spanning citation networks (Cora, Citeseer, Cora-ML, DBLP), social/web networks (Blog, Wiki), and infrastructure (Air, Survey). The model was benchmarked against 21 state-of-the-art techniques, including standard GNNs like GCN and GAT, as well as specialized digraph methods like DiGCN and MagNet.
Results and Discussion
D-HYPR consistently outperforms existing methods across various tasks. In link prediction, it achieved a 21.43% relative gain in Average Precision (AP) on the Cora dataset using only 4-dimensional embeddings. For node classification, D-HYPR demonstrates superior robustness, particularly in low-label regimes where only 1-10% of nodes are labeled, as illustrated in Figure 2.
One of the most significant findings is the efficiency of hyperbolic space. In a 4-dimensional space, D-HYPR often outperforms other models using 32 or more dimensions. This provides a significant advantage for large-scale applications where memory and computation are limited.
Conclusion
The success of D-HYPR highlights the importance of capturing the inherent asymmetry and hierarchical nature of digraphs. By integrating hyperbolic geometry with collaborative neighborhood modeling, the framework achieves state-of-the-art performance with high efficiency. Future research will explore extending these techniques to heterogeneous and dynamic digraphs, as well as scaling to networks with billions of edges.
Summary updated