Harnessing Neighborhood Modeling and Asymmetry Preservation for Digraph Representation Learning

Honglu Zhou, Advith Chegu, Samuel S. Sohn, Zuohui Fu, Gerard de Melo, Mubbasir Kapadia

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:

  1. 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.
  2. 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.
  3. 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.
Figure 1: Distribution of neighborhood types in the Cora dataset, highlighting the prevalence of common-in neighbors.

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.

Figure 2: Performance comparison of D-HYPR against baselines on CiteSeer and Cora-ML datasets across varying label rates.

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

Abstract

Digraph Representation Learning aims to learn representations for directed homogeneous graphs (digraphs). Prior work is largely constrained or has poor generalizability across tasks. Most Graph Neural Networks exhibit poor performance on digraphs due to the neglect of modeling neighborhoods and preserving asymmetry. In this paper, we address these notable challenges by leveraging hyperbolic collaborative learning from multi-ordered partitioned neighborhoods and asymmetry-preserving regularizers. Our resulting formalism, Digraph Hyperbolic Networks (D-HYPR), is versatile for multiple tasks including node classification, link presence prediction, and link property prediction. The efficacy of D-HYPR was meticulously examined against 21 previous techniques, using 8 real-world digraph datasets. D-HYPR statistically significantly outperforms the current state of the art. We release our code at https://github. com/hongluzhou/dhypr.
BibTeX
@inproceedings{zhou2023harnessing,
  author = {Honglu Zhou and Advith Chegu and Samuel S. Sohn and Zuohui Fu and Gerard de Melo and Mubbasir Kapadia},
  title = {{Harnessing Neighborhood Modeling and Asymmetry Preservation for Digraph Representation Learning}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2023},
  doi = {10.24963/ijcai.2023/731},
}
Figure