Harnessing Neighborhood Modeling and Asymmetry Preservation for Digraph Representation Learning

1 Introduction

Directionality is intrinsic to numerous real-world graphs [Ou et al., 2016]. Digraph Representation Learning (DRL) aims to learn representations for directed homogeneous graphs (digraphs) [Tong et al., 2020a; Zhang et al., 2021a]. Early DRL techniques include factorization and random walk-based approaches [Ou et al., 2016; Sun et al., 2019; Zhou et al., 2017; Khosla et al., 2019]. Yet, these methods face scalability issues or sensitivity to noise. Graph Neural Networks (GNNs) have seen recent success [Zhou et al., 2020], but they mainly focus on undirected graphs. There are two notable challenges that hinder their effectiveness on digraphs.

Challenge 1: Neighborhood Modeling. Node neighborhoods in a graph can carry distinct semantic meanings. Existing GNN techniques often simplify digraphs to undirected graphs or consider only direct out-neighbors [Kipf and Welling, 2016b; Veliˇckovi´c et al., 2017; Chami et al., 2019;

∗ Published at the 31st ACM International Conference on Information & Knowledge Management - Received the Best Paper Award

Zhu et al., 2020], which can lead to a loss of original structure and ultimately subpar results on digraph-specific tasks.

Challenge 2: Asymmetry Preservation. Learning objectives based on symmetrical measures used by popular GNNs fail to capture asymmetric connections in digraphs [Salha et al., 2019]. Applications based on link prediction or graph topology learning are particularly affected when models fail to preserve digraph structural asymmetry.

Spectral-based DRL GNNs have sought to address the first challenge but struggle when applying models to graphs with different structures [Zhang et al., 2021a]. Solutions for the second challenge, such as viewing edge directions as edge features [Gong and Cheng, 2019] or parametrizing the node pair likelihood function by a neural network [Shi et al., 2019], neglect the first challenge. Moreover, prior DRL techniques are often constrained to directed acyclic graphs [Thost and Chen, 2021], are transductive [Sim et al., 2021], or lack broad applicability and generalizability across tasks [Sim et al., 2021; Tong et al., 2020b; Ma et al., 2019].

We propose Digraph HYPERbolic Networks (D-HYPR), which use hyperbolic collaborative learning and asymmetrypreserving regularizers to tackle these challenges. Our approach comprises: (1) Modeling node neighborhoods using collaborative learning from multi-ordered and partitioned neighborhoods with larger receptive fields, (2) Using hyperbolic space to avoid distortion in neighborhood modeling, (3) Preserving asymmetry with socio-psychology-inspired regularizers, and (4) Ensuring flexibility through a messagepassing-based GNN formalism for general digraphs.

Our contributions are three-fold: (1) D-HYPR that considers unique node neighborhoods and asymmetric relationships in digraphs, (2) Benchmarking across 8 real-world digraphs and 21 prior methods, revealing D-HYPR's superiority, and (3) Capability of generating meaningful low-dimensional embeddings, an efficiency boon for large-scale applications.

2 Preliminaries

Let G = (V, E) be a homogeneous graph with vertex set V and edge set E; e ∈ E is an ordered pair e = (i, j) between vertices i and j. The adjacency matrix of G can be denoted as A = {0, 1}|V|×|V| . G is a digraph when ∃(i, j), Ai,j ̸= Aj,i. Nodes are described by a feature matrix X0,E ∈ R|V|×d , i.e., each node i ∈ V has a d-dimensional Euclidean feature x0,E i .

The superscript E indicates that the vector lies in a Euclidean space, while H denotes a hyperbolic vector. 0 denotes the input layer. The goal of DRL is to learn a mapping

that maps nodes to low-dimensional (d′ ≪ |V|) vectors.

The Poincar´e ball model [Ganea et al., 2018] is defined by the n-dimensional manifold Dnc = {x ∈ Rn : c ∥x∥ < 1} equipped with the Riemannian metric: gcx = λ2x gE , where λx := 2 1-c∥x∥2 , gE = In is the Euclidean metric tensor, and c > 0 (we refer to -c as the curvature). Dnc is the open ball of radius 1/√c. The connections between hyperbolic space and tangent space are established by the exponential map expcx : TxDnc →Dnc and logarithmic map logcx : Dnc → TxDnc :

where x, y ∈ Dnc , v ∈ TxDnc , and ⊕c denotes M¨obius addition, and

The M¨obius scalar multiplication (Eq. 5) and M¨obius matrix multiplication of x ∈ Dnc \{0} (Eq. 6) are

where r ∈ R and M ∈ Rm×n . The induced distance function on (Dnc , gc ) is given by

3 Methodology

Hyperbolic Embedding Learning. D-HYPR utilizes hyperbolic GNNs over Euclidean counterparts as the backbone for DRL. Given G and x0,E i , we obtain x0,H i by applying expc0 0 (·), where c0 is learned in training. Hyperbolic message passing (Eqs. 8 to 10) is then performed by multiple layers, forming the Hyperbolic Graph Embedding Layers. The layer is indexed by ℓ, ranging from 1 to a pre-defined integer l. (1) Hyperbolic Feature Transformation is performed by

where W ℓ ∈ RF ℓ×F ℓ-1 is the weight matrix, and b ∈ DF ℓ cℓ-1 denotes the bias (both are learned).

(2) Hyperbolic Neighbor Aggregation results in hℓ,H i ,

where N(i) = {j : (i, j) ∈ E} denotes the set of neighbors of i ∈ V. We apply out-degree normalization of the adjacency matrix to obtain the aggregation weights eij .

(3) Non-Linear Activation with Trainable Curvatures. The output hyperbolic representation of node i in layer ℓ is set as

where σ(·) represents the ReLU non-linearity function.

Neighborhood Collaborative Learning. D-HYPR considers four primary neighborhood types. To achieve this, four types of k-order proximity matrix are defined:

(1) diffusion in Akdin ,

where A1din = A⊺ , · is the inner product and 1 is the indicator function. Akdin (i, j) = 1 if there is a directed path from node j to node i of length exactly k. (2) diffusion out Akdout ,

where A1dout = A. Akdout (i, j) = 1 if there is a directed path from node i to node j of length exactly k.

(3) common in Akcin ,

where i ̸= j ̸= p. Akcin (i, j) = 1 if node i and node j have a common in-neighbor k hops away.

(4) common out Akcout ,

where i ̸= j ̸= p. Akcout (i, j) = 1 if node i and node j have a common out-neighbor k hops away.

We compute these matrices for k = 1 to K (K is a hyperparameter) which replace the adjacency matrix as input to Hyperbolic Graph Embedding Layers that output 4K hyperbolic vectors. Subsequently, the hyperbolic average of the 4K vectors yields zfuse i . We then apply Eq. (9) with the learned curvature -cl and equal aggregation weights. The resulting output, zl,H i , is the final hyperbolic embedding of node i.

Asymmetry-Preserving Regularizers. We adopt the hyperbolic Fermi-Dirac decoder [Krioukov et al., 2010] to account for homophily [McPherson et al., 2001]. The decoder defines the likelihood of a node pair (i, j) as

where r=2 and t=1 (default), and dDd′ cl (·, ·) is defined in Eq. 7.

We then preserve the individual asymmetric node connectivity to account for preferential attachment [Mitzenmacher,

2004] by learning a mass for each node. This design [Salha et al., 2019] is derived from Newton's theory of universal gravitation. To incorporate this design into D-HYPR based in hyperbolic space instead of Euclidean, we first perform zl,E i = logcl 0 (zl,H i ), and then employ a Euclidean linear layer to learn mi ∈ R (mass of node i). The likelihood of node pair (i, j) is computed by

where γ(·) denotes the sigmoid function, and λ ∈ R is a hyper-parameter. p(i, j)g ̸= p(j, i)g. Eqs. (16) and (15) both serve as self-supervised regularizers by minimizing the binary cross-entropy loss with negative sampling to estimate the likelihood of each node pair. However, Eq. (16) is employed one layer after where Eq. (15) is used. Thus, even though dDd′ cl (·, ·) also appears in Eq. (16), we find that Eq. (15) provides auxiliary guidance for the model to better construct the final hyperbolic embedding space.

4 Experiments

In all tables, the best score is bolded, the second best is underlined, and the third best is in italic. Relative gains are computed as (BEST - SECOND)/SECOND. ∗ indicates statistically superior performance of the best to the second best at a significance level of 0.001 using a standard paired t-test. Values after ± are standard deviations.

NeighborhoodAnalyses. We provide neighborhood analyses of datasets in Fig. 1, where pie charts show the ratio of the 4 types of neighborhoods in each dataset (K=1). Unlike the diffusion in/out neighborhood that traditional GNNs typically use, common in/out neighborhood consists of more neighbors, which suggests that neighborhood collaborative learning benefits from encoding additional context. For each neighborhood type, we also plot a histogram showing the distribution of the number of neighbors a node has over the entire graph. We observe asymptotical power-law nodedegree distributions (i.e., scale-free) for most neighborhoods. Link Prediction (LP). We list the results in Table 2 and Table 3. One advantage of hyperbolic digraph embedding is low data distortion even with a low-dimensional embedding space. The superior performance of D-HYPR is evidentthe highest relative gain of D-HYPR is 21.43% on AP over the Cora dataset. As the dimensionality increases, the gap from D-HYPR to the other methods decreases, but D-HYPR remains the best-performing method.

Semi-supervised Node Classification (NC). We follow prior work [Grover and Leskovec, 2016] in reporting the results when the number of nodes labeled for training is varied between 1% and 10%. According to Fig. 2, D-HYPR consistently outperforms the baselines, and tends to perform well at fairly low label rates. D-HYPR statistical significantly outperforms the state-of-the-art (SOTA) methods.

Link Sign Prediction (SP). Table 1 reports the results which show D-HYPR is the most effective GNN model. Similar to LP and NC tasks, the effectiveness of D-HYPR is the most striking using a 4 dimensional embedding space.

Please refer to [Zhou et al., 2022] for additional details regarding the datasets and experimental setup, as well as additional analyses and comparisons with more SOTA techniques.

5 Conclusion

We propose D-HYPR: the Digraph HYPERbolic Network, as a novel GNN-based formalism for Digraph Representation Learning (DRL) by addressing Neighborhood Modeling and Asymmetry Preservation. Through rigorous evaluation, we empirically demonstrate the superiority of D-HYPR. D-HYPR retains effectiveness given a low budget of embedding dimensionality or labeled training samples, which is desirable for real-world applications.

Acknowledgments

The research was supported in part by NSF awards: IIS1703883, IIS-1955404, IIS-1955365, RETTL-2119265, and EAGER-2122119. This material is based upon work supported by the U.S. Department of Homeland Security under Grant Award Number 22STESE00001 01 01.

Disclaimer: The views and conclusions contained in this document are those of the authors and should not be interpreted as necessarily representing the official policies, either expressed or implied, of the U.S. Department of Homeland Security.