Exploring the Role of Node Diversity in Directed Graph Representation Learning

1 Introduction

Graph neural networks (GNNs) have achieved great success by analyzing the undirected graph to extract representation from the graph data. However, many graphs are directed where each edge is bidirectional in real applications, such as traffic networks and web page networks. As a result, many previous GNNs considering undirected graphs (e.g., [Kipf and Welling, 2017; Hamilton et al., 2017; Velickovic et al., 2018; Yang et al., 2023b; Yang et al., 2023a; Bi et al., 2022b; Mo et al., 2023; Mo et al., 2024; Huang et al., 2023a]) ignore the directional information, and thus resulting in discarding valuable information crucial for downstream tasks [Rossi et al., 2023]. For example, in the web page network, web pages pointed to more links tend to have more traffic. If the directional information of the web page network is ignored, some web pages with few incoming edges and much outgoing edges will be predicted as high-traffic web pages. Hence, it is practical to consider the directional information for applying GNNs in the directed graphs.

∗Corresponding authors: X. Zhu and Z. Zhang

Previous GNN methods for directed graphs primarily focus on delineating the directional information in the graph, including spectral DGNN methods [Zhang et al., 2021; Tong et al., 2020a; Tong et al., 2021] and spatial DGNN methods [Rossi et al., 2023; Tong et al., 2020b]. The spectral DGNN methods mainly focus on constructing the Laplacian matrix with the directional information. For example, DiGCN [Tong et al., 2020a] employs the transfer probability of personalized PageRank to approximate the Laplace matrix of directed graphs for considering the directional information [Brin, 1998]. MagNet [Zhang et al., 2021] designs the magnetic Laplacian matrix to capture directional information by a phase matrix. However, many directed spectral methods use the same mapping function to obtain node representation for the outgoing information and the incoming information, and thus they may not output discriminative representation by ignoring the difference between the incoming information and the outgoing information [Rossi et al., 2023].

Spatial DGNN methods are designed to first learn different mapping functions for incoming and outgoing information, and then combine two directional information to update node representation for downstream tasks. For example, DGCN [Tong et al., 2020b] separately learns mapping functions for directional information based on their second-order information. Dir-GNN [Rossi et al., 2023] first learns different mapping functions based on the first-order information of nodes, and then manually assigns weights to fuse these two kinds of node representation obtained from two mapping functions. To summarize, previous spatial DGNNs methods consider the difference between two kinds of directional information by two ways, i.e., different mapping functions and manually setting different weights on the node representation learned from different directional information, but they still have limitations to be addressed.

First, the representation of every node is affected by its neighbors, which include an in-neighbor set and an outneighbor set in the directed graph. The label of every node is determined by either the in-neighbor set or the out-neighbor set or even both sets, as shown in Figure 1. Hence, every node in either in-neighbors or out-neighbors should have different weights, neighbor diversity for short. However, previous spatial DGNNs assign them with the same weight. Second, degree can reflect the centrality of a node and provide information about its surrounding structure. Moreover, degree information is very helpful for distinguishing two different nodes, especially in directed graphs including in-degree and out-degree. In particular, every node has different in-degree and out-degree, i.e., degree diversity. However, previous spatial DGNNs ignore the degree information in directed graphs to weaken the representation ability of the node. Obviously, both neighbor diversity and degree diversity show the characteristics of nodes, i.e., node diversity.

In this paper, we propose a new spatial DGNN method, namely Node Diversity Directed Graph Neural Network (NDDGNN) shown in Figure 3, to model directional information for graph representation learning by considering node diversity. To do this, we follow the directed spatial methods to construct different mapping functions for the outgoing information and the incoming information. During the construction process, different from these previous spatial DGNNs assigning the same weight to all nodes in the same neighbor set (i.e., out-neighbor set and in-neighbor set) for every node, our method assigns them with different weights by considering node diversity. Specifically, we consider neighbor diversity by defining in-Dirichlet energy and out-Dirichlet energy to encode the dissimilarity between every node and its neighbor and consider degree diversity by introducing degree embedding to encode in-degree information and out-degree information.

Compared to previous DGNNs, the main contributions of our method are summarized as follows:

• We first observe node diversity for representation learning in directed graphs and then propose a new directed GNN method considering node diversity (including neighbor diversity and degree diversity) for graph representation learning. As a result, our method is able to adaptively learn weights for every node.
• We experimentally verify on real-world datasets the superiority of our proposed method, compared to SOTA methods, in terms of node classification and link prediction.

2 Methodology

Let G = (V,E,X,Y) be a directed and unweighted graph, where V = {vi|i = 1, 2, . . . , n}, E = {(vi, vj)|vi, vj ∈ V}, X ∈ Rn×f , and Y ∈ Rn×c , respectively, denote the node set, the edge set, the node feature matrix and the label matrix, and A ∈ {0, 1}n×n be the adjacency matrix of the graph G, D = ∑i Ai,j is the degree matrix, and ˜∆ = I -D- 12AD- 12 is the normalize Laplacian matrix. By denoting Ni,→ as the out-going neighbor set of the i-th node vi and D→ = ∑j (Ai,j) as the out-degree diagonal matrix, we obtain the symmetric normalize directed out-neighbor matrix S→ = D- 12 → AD- 12 ← and rownormalize directed out-neighbor matrix S′→ = D-1 → A. Similarly, we can define Ni,←, D←, S← = ST→ and S′← = S′T→.

2.1 Motivation

To deal with the directional information in the directed graph, previous spatial DGNNs first separate the directional information into incoming information and outgoing information, and then learn individual mapping functions for them, i.e., the outgoing mapping function and the incoming mapping function. Each function outputs one kind of representation for every node. Specifically, following DirGNN [Rossi et al., 2023] to denote two directional representation as S→H(l)W(l) → and S←H(l)W(l) → , where W(l) → andW(l) ← , respectively, represent the learnable weights, we fuse them by manually assigning a hyper-parameter to update the node representation H(l+1) in the (l + 1)-th layer by:

where γ is the hyper-parameter. Although the weight γ is set to distinguish two kinds of directional information, it actually assigns the same weight to every node representation in the same mapping information. This leaves at least two issues to be addressed. First, the hyper-parameter γ easily results in expensive computation cost. Second, all nodes share the same weight for two kinds of directional information by ignoring node diversity.

In this paper, we propose a new spatial directed graph neural network framework shown in Figure 3 to address the above issues.

2.2 Node Diversity

There are many facts to result in node diversity. For example, neighbor diversity, degree diversity, structure diversity, e.t.c. For simplicity, in this paper, we investigate node diversity by focusing on neighbor diversity and degree diversity.

Neighbor Diversity

Previous spatial DGNNs assign the same weight to all nodes in the same neighbor set, by ignoring neighbor diversity. Given an example in Figure 2, the label of the centric node in the left of Figure 2 is benefited from its out-neighbors because it and its out-neighbor have the same color, while the label of the centric node in the middle of Figure 2 is benefited from its in-neighbors. In this case, it is obvious that the different nodes has different weights to either in-neighbor set and out-neighbor set. However, previous spatial DGNNs assign them with the same weight. In this section, we consider neighbor diversity to assign them with different weights.

The out-neighbor set of every node is different from the set of other nodes, while the in-neighbor set of every node is different from the one of other nodes. Therefore, it is reasonable to learn different weights for the out-neighbor set and the in-neighbor set. The category of every node is related to the majority class in the neighbor set (i.e., either out-neighbor set or in-neighbor set). Specifically, if the category of every node is same as the category of the majority class in the neighbor set, the weight of this neighbor set should be large for achieving small intra-class difference. Since we have label information of a part of nodes, so the feature difference between every node and its connected nodes can be used to measure the intra-class difference, and thus determining the weights of the neighbor-set. Considering Dirichlet energy [Xu et al., 2023] is one of popular ways to measure the adjacent node feature difference, in this paper, we employ it to guide to learn the weights. Specifically, given the node representation H = [h1, h2, . . . , hn] ∈ Rn×f , the Dirichlet energy of l layer E (H(l) ) is defined as follows:

where s′ij denotes weight of edges.

Since different dimensions carry different information, it is necessary to assign different weights to different dimensions. However, Dirichlet energy assigns the same weight to all dimensions. In this paper, we introduce learnable parameters in Dirichlet energy, enabling the model to assign distinct weights to different dimensions and can be adaptively adjusted according to downstream tasks, which can be written as:

where w(l) ∈ Rf×1 is a learnable parameter vector and ⊙ is element-wise product.

Although Dirichlet energy is used to compute the whole graph, we focus on the difference between every node and its neighbor sets. To facilitate subsequent calculations and reduce complexity, we use row directed normalized adjacency matrix for s′ij here (i.e., s′ij,← = 1 di,← , s′ij,→ = 1 di,→ ). Thus, for out-neighbor set of all nodes, the matrix form of out-

��� �������

��� ��������

Figure 4: A case to illustrate the difference of weight assignment between previous spatial DGNN (e.g., Dir-GNN [Rossi et al., 2023]) and our proposed method.

Dirichlet energy e(l) → in l layer can be defined as follows:

where e(l) → ∈ Rn×1 , which i-th element represents the outDirichlet energy of node i and I is the identity matrix. The same as in-Dirichlet energy e(l) ← for in-neighbor set:

On large-scale graphs, to reduce the time complexity, we rewrite equation (3) as:

This equation calculates the difference between each node and two neighbors like equation (3) and ignores the variance within the neighbors, we prove it in Appendix. Thus, the out-Dirichlet energy in equation (4) can be write as:e(l) → = (H - SH)2w(l) → , the same as in-Dirichlet energy. Here, we have extended the Dirichlet energy to adaptively characterize the differences between each node and its in-neighbors and out-neighbors in directed graphs. However, there is a problem in using the corresponding Dirichlet energy as the weights of two kinds of neighbor sets. In general, the larger the difference in features between a node and its neighbors, the more likely they belong to different categories. Therefore, directly using Dirichlet energy as weights would lead to assigning larger weights to the neighbor set with more different categories nodes and smaller weights to the neighbor sets with more same categories nodes. This is contrary to our motivation. Therefore, we add the inverse to correct them.

where every element of q(l) → ∈ Rn×1 and q(l) ← ∈ Rn×1 are adaptive weights of the two kinds of neighbor set for every node, respectively.

Different from current spatial DGNNs manually set the weight, Eq. (7) automatically learning q(l) → and q(l) ← by considering the difference between every node and its neighbors by in-Dirichlet energy and out-Dirichlet energy. As a result, for all nodes, the neighbor sets with smaller feature differences (i.e., more similar categories), larger weights will be assigned compared to the other neighbor set. i.e., characterizing neighbor diversity for every node. However, ever node is related to its neighbors as well as its degree, which also needs to be paid attention on node diversity.

Degree Diversity

Previous spatial DGNNs combine the in-neighbors and outneighbors without considering the in-degree and out-degree. However, degree information can improve GNNs's ability to distinguish the different nodes, especially in directed graphs since there are two types of degree. For example, as shown in Figure 2, for simply analysis, we assume that nodes of the same category have the same features. The previous spatial DGNNs utilize the equation 1 to update nodes representation for nodes in left and right of Figure 2, the two nodes would obtain the same representations. However these two nodes are not the same node because their number of neighbors are different (i.e., in-degree and out-degree). Therefore, without considering degree information will weaken the node representation ability of DGNNs.

In this paper, to overcome above issue, we propose to learn degree embedding for integrating degree information with the process of representation learning. Specifically, denoting Deg← ∈ Rn×f and Deg→ ∈ Rn×f , as learneable in-degree embedding and out-degree embedding, respectively, Eq. ( 7) becomes:

Based on Eq. (8), nodes with the same in-degree have the same in-degree embedding. Similarly, nodes with the same out-degree also have the same out-degree embedding. Hence, when two nodes share same in out-/in-degrees and out-/in-neighbor differences, their weights during aggregation will be similar. In contrast, even if two nodes have very similar features for themselves and their neighbors, as long as their degree information is different they will not be mapped to the same point in the feature space (i.e., the model has the ability to distinguish between the two nodes). However, previous spatial DGNNs by [Rossi et al., 2023; Tong et al., 2020a] assign the same weight to both nodes in all cases.

Overall Architecture

To consider the node diversity in directed graph, we propose a simple but effective framework called NDDGNN as shown in Figure 3. Specifically, for a directed graph, we learn the weights vector (i.e., q(l) ← , q(l) → ∈ Rn×1 ), where q(l) i,← and q(l) i,→ are in-neighbor and out-neighbor weight of node i in layer l, respectively. Then through the softmax normalize to ensure the q(l) ← + q(l) → = [1, 1, · · · , 1]T as follow:

where diag(Γ(l) → ) stands for the diagonal value of diagonal matrix Γ(l) → . Moreover, the equation holds, i.e., Γ(l) ← = I - Γ(l) → .

In this paper, we take into account node diversity to overcome the issues in previous spatial DGNNs by using Eq. (10) to update node representation H(l+1) in the (l + 1)-th layer.

H(l+1) = Γ(l) → S→H(l)W(l) → + Γ(l) ← S←H(l)W(l) ← , (10) where Γ(l) ← ∈ Rn×n is the diagonal matrix consisting of [Γ(l) (1,1)←, Γ(l) (2,2)←, . . . , Γ(l) (n,n)←] as the diagonal elements in l layer, including both neighbor diversity and degree diversity, the same as Γ→. With this form, it is possible to achieve that each node has different weights assigned to outgoing and incoming neighbors. The difference between previous spatial DGNNs (e.g., DirGNN) and our proposed method is shown in Figure 4, where previous spatial DGNNs is a special case of our proposed method in Eq. (10).

By aggregating the neighbors' representation and the node representation in the previous layer, in this paper, node representation H(l+1) in the (l + 1)-th layer of our proposed method is updated by:

where α is a hyper-parameter to preserve the information of the previous layer. We show the model's real running time in the Appendix.

2.3 Consistency Regularization.

In our method, we decompose the directional information into incoming information and outgoing information. We expect that weights learnt for incoming information follow the same distribution, while weights learnt from outgoing information also follow the same distribution. To do this, we propose the consistency regularization to mitigate and avoid learning the abnormal weights that deviate from the distribution. Specifically, we first calculate the average of all weights for either incoming information or outgoing information by:

We then propose to minimize the distance between γ→ and Γi,→, as well as the distance between γ← and Γi,← by:

2.4 Objective Function

In each epoch, we employ both the cross entropy loss and the consistency regularization loss in Eq. (13) to conduct representation learning. The final objective function of the proposed method is formulated as:

where Lsup is the cross entropy loss and λ is a hyperparameter to balance two losses.

3 Experiments

3.1 Experimental Setting

Datasets

We evaluate the effectiveness of the proposed method on 2 homophilic datasets and 5 heterophilic datasets. Homophilic datasets include Cora-ML and Citeseer-Full [Bojchevski and G¨unnemann, 2018]. Heterophilic datasets include Chameleon, Squirrel [Pei et al., 2020], Roman-Empire [Platonov et al., 2023], Arxiv-Year [Leskovec et al., 2005], and Snap-Patents [Leskovec and Krevl, 2014]. In particular, Arxiv-Year and Snap-Patents are large-scale datasets. More details of the used datasets can be found in Appendix.

Comparison Methods

The comparison methods include 3 traditional undirected graph methods (i.e., GCN [Kipf and Welling, 2017], GAT [Velickovic et al., 2018], and graphSAGE [Hamilton et al., 2017]), 6 state-of-the-art undirected graph methods (i.e., H2GCN [Zhu et al., 2020], GPRGNN [Chien et al., 2021], LINKX [Lim et al., 2021], FSGNN [Maurya et al., 2021], ACM-GCN [Luan et al., 2022], DloGNN [Li et al., 2022], and Gradient Gating [Rusch et al., 2023]), and three state-of-the-art directed graph methods (i.e., DiGCN [Tong et al., 2020a], MagNet [Zhang et al., 2021] and Dir-GNN [Rossi et al., 2023]).

Evaluation Protocol

To evaluate the effectiveness of the proposed method, we follow the settings in [Rossi et al., 2023] to conduct node classification tasks and link prediction tasks. Specifically, for the node classification task, we split all datasets in Dir-GNN [Rossi et al., 2023] and the detail can be found in the Appendix. For directed graph link prediction task, we remove 10% of edges for testing, 5% for validation, and use the rest of the edges for training. We randomly generate 10 splits for each graph and the graph connectivity is maintained during the splitting.

Setting-Up

We conduct all experiments on a server with Nvidia RTX 4090 (24GB memory each). We employ early stopping on the validation accuracy for each experiment. Moreover, we conduct each experiment on ten random seeds and report the average results.

In the proposed method, we optimize all parameters by the Adam optimization [Kingma and Ba, 2015] with the learning rate in the range of {0.005, 0.01} and set the weight decay as 0. Moreover, we set the number of model layers in the range of {4, 5, 6}, set the dropout in the range of {0.0, 0.35, 0.5, 0.6}, and set the size of the hidden unit in the range of {32, 128, 256}. We set α for preserving the representation of the previous layer in the range of {0.0, 0.3, 0.5, 0.8, 1.0}, and set λ in our regularization term in the range of {0.0, 0.1, 0.2, 0.9}. Notably, we employ the same parameters for both node classification and link prediction tasks. In addition, we set the parameters of all comparison methods according to the original literature so that they output the best performance.

3.2 Results Analysis

Node Classification

We evaluate the effectiveness of our method on the node classification task and report the classification accuracy of all methods on all datasets in Table 1. Obviously, the proposed method achieves the best performance on all datasets.

First, compared with the undirected graph methods (i.e., GCN, GAT, graph-SAGE, H2GCN, GPRGNN, LINKX, FSGNN, ACM-GCN, DloGNN, and Grand.Gating), the proposed method consistently obtains substantial improvements. For example, the proposed method on average improves by 11.5%, 13.81%, 8.38%, 11.12%, 1.72%, 4.65%, and 9.6%, compared with the best undirected graph method Grand.Gating on all datasets. This can be attributed to the fact that these state-of-the-art undirected graph methods are primarily designed to operate on symmetric graphs, thus their architectures might not be well-suited to effectively handle the inherent directional information present in directed graphs. More seriously, directly applying undirected graph methods to directed graph datasets can even introduce negative effects. For example, MLP outperforms many undirected graph methods (e.g., GCN, GAT, H2GCN, and GPRGNN) on directed datasets (e.g., Cora-ML and Citeseer). This suggests that these undirected graph methods act as a negative impact for the utilization of the graph structure.

Second, compared with the directed graph methods, the proposed method achieves the best performance, followed by Dir-GNN, MagNet and Di-GCN. For example, the proposed method on average improves by 0.99%, compared with the best directed graph method Dir-GNN on all datasets. This suggests that the proposed framework that it is effective to take node diversity into account, compared to directed graph methods.

Link Prediction

We evaluate the effectiveness of the proposed method on the link prediction tasks by reporting the results (i.e., prediction accuracy) on four datasets in Table 2. We can observe that our method consistently achieves the best performance compared to the directed graph methods. For example, the proposed method average improves by 0.84%, 2.04%, 4.02%, and 2.27%, compared with the best directed graph method MagNet on all datasets. This indicates that our method can achieve good performance in structure-dominated tasks.

Effectiveness on Nodes with Complex Structure

We further evaluate the effectiveness of the proposed method to cope with complex structure (e.g., nodes with extremely different out-degree and in-degree) in directed graphs. To do this, we select the top 5% nodes with the largest outdegree-in-degree differences and visualize the classification performance on four datasets in Figure 5. First, the undirected graph method GCN almost loses its representation ability for complex structural cases in directed graphs, especially in the Chameleon and Squirrel datasets where the maximum degree difference is more than a thousand. This is due to the inability of undirected graph methods to capture such differences. Second, the proposed NDDGNN achieves the best performance on complex nodes compared to other directed graph methods, which benefits from node diversity.

Ablation Study

The proposed method mainly consists of three components, i.e., neighbor diversity (i.e., +N), degree diversity (i.e., +Deg) and consistency loss (i.e., +Lcon). To verify the effectiveness of each component in the proposed method, we investigate the performance of all variants (except Lcon, since Lcon depends on +N or +Deg) on the node classification task by reporting the results in Table 3.

First, the variant method that considers both the neighbour diversity and the degree diversity leads to a large performance improvement, compared with the variant method considering only one diversity of them. This suggests that both neighborhood diversity and degree diversity are critical and not interchangeable. Second, the variant method that considers the consistency loss averagely improves by 3.45%, compared with the counterpart variant methods without the consistency loss. This indicates that the consistency loss avoids learning the abnormal weights to some extent. Therefore, the effectiveness of each component of the proposed method is verified.

4 RelatedWork

We briefly review the study related to this work, i.e., directed graph mining methods and adaptive node level methods.

4.1 Directed GraphMiningMethods

[Ma et al., 2019] constructs a directed Laplacian matrix based on identities that involve the random walk matrix and its stationary distribution.

DGCN [Tong et al., 2020b] leverages both the first-order and second-order proximity information to collectively describe and distinguish the neighborhood of each vertex from those vertices. MotifNet [Monti et al., 2018] is capable of dealing with directed graphs by exploiting local graph motifs. MagNet [Zhang et al., 2021] utilizes the magnetic Laplacian matrix to encode undirected geometric structures in the magnitudes and directional information in the phases. DiGCN [Tong et al., 2020a] defines the Laplacian matrix of the directed graph based on PageRank. [Tong et al., 2021] extends DiGCN to obtain different Laplacian matrices under different hyper-parameters. Recently, Dir-GNN [Rossi et al., 2023] proposes first aggregating outgoing and incoming information separately, and then simply fusing the information of outgoing and incoming information with a fixed hyper-parameter weight for all nodes.

4.2 Graph Neural Networks With Adaptive Node Level Methods

GNN [Kipf and Welling, 2017; Yang et al., 2023b; Yang et al., 2023a; Bi et al., 2022a] have shown excellent performance on graph representation learning. Some methods utilize the adaptive weight assignment technique to let nodes learn the appropriate representation. Such as GAT [Velickovic et al., 2018] adaptively assigns weights to the neighbors of each node using attention mechanisms, SA-GNN [Huang et al., 2023b] adopts different aggregation methods for homophilic and heterophilic neighbors for each node by classifying neighbor labels. Similarly, GBK-GNN [Du et al., 2022] uses the bi-kernel to go through the homophily information of the modeled neighbors for each node. MM-GNN [Bi et al., 2023] models the multi-order moments' information for every node. However, the previous methods did not consider the complex situation of having two kinds of neighbors and two degrees in a directed graph.

5 Conclusion

In this paper, we proposed a new directed GNN method to deal with the directional information by considering the node diversity. For specificity, the node diversity is only composed of neighbor diversity and degree diversity. Moreover, our method investigates two kinds of node diversity to guide the assignments of node-level weights. Experimental results demonstrated the effectiveness of our proposed method, compared to SOTA methods in terms of node classification and link prediction tasks.

Acknowledgments

This work was supported in part by the National Key Research and Development Program of China under Grant 2022YFA1004100.