Graph Entropy Guided Node Embedding Dimension Selection for Graph Neural Networks

1 Introduction

In recent years, Graph Neural Networks (GNNs) [Wu et al., 2020; Xie et al., 2020] have attracted tremendous attention from both research and industry, due to its powerful representation capability for large amounts of graph structured data in practice, e.g., social networks, citation networks, road networks. GNNs are mostly used to compute distributed node representations (a.k.a. embeddings), as dense vectors, which serves as the key to various downstream tasks in graph related applications [Peng et al., 2019; Sun et al., 2021]. The dimension of node embedding, as a crucial hyperparameter, has a significant influence on the performance of GNNs. First, node embeddings with too small dimensions limit the information expressiveness of nodes, whereas those with too large dimensions suffer from overfitting. Second, the number of parameters of GNNs that build on node embeddings is usually a linear or quadratic function of node embedding dimension, which directly affects model complexity and computational efficiency [Yin and Shen, 2018].

However, we often have no idea towards the appropriate dimension of node embedding and have to rely on grid search or domain knowledge to adjust it as a model hyperparameter given a new graph. These approaches often suffer from the following problems: 1) Choosing node embedding dimension by empirical experience can easily lead to poor model performances. 2) Experimental strategies such as grid search are resource-consuming and timeconsuming. This raises the questions of what is the appropriate dimension of node embedding for given graphs and what should we base on to choose such dimension? Recently, several researchers [Liu et al., 2020; Zhu et al., 2018; Shen et al., 2020] have attempt to tackle these problems through dimensionality reduction. However, these methods focus on choosing important features or using complex matrix transformation to reduce from a large dimension instead of direct selection based on the graph. Moreover, different from sequence and image data, graph data contains rich link topology. The general dimensionality reduction methods only consider node features but ignore it for GNNs, which results in loss of useful information.

In this paper, inspired by recent dimension selection works [Yin and Shen, 2018; Hung and Yamanishi, 2020] in Natural Language Processing (NLP), we revisit NEDS from the perspective of minimum entropy principle [Zhu et al., 1997]. Specifically, entropy is a natural way to measure the uncertainty of the dimension, the principle of minimum entropy motivates us to choose an ideal node embedding dimension for any given graphs by minimizing the uncertainty of the graph. As shown in Fig. 1, we design a novel graph entropy that contains feature entropy and structure entropy to account for the information regarding both node features and link structures on graphs. Subsequently, we propose a novel Minimum Graph Entropy (MinGE) algorithm 1 to directly select an appropriate node embedding dimension for a given graph through minimizing the graph entropy. As a consequence, MinGE leads to appropriate NEDS without the need of additional domain knowledge, and is obviously more efficient than grid search.

The main contributions of this paper are summarized as follows: (1) We stress the importance of direct NEDS for GNNs on arbitrary graphs and revisit it from an intuitive perspective based on the principle of minimum entropy. (2) We develop the MinGE algorithm based on our novel design of graph entropy to enable direct NEDS, which considers the rich feature and structure information on graphs. (3) Experimental results with several popular GNNs such as GCN, GAT, and GCNII over node classification and link prediction tasks on benchmark datasets demonstrate the effectiveness and generalizability of our proposed MinGE algorithm.

2 RelatedWork

Dimension Selection. How to choose the appropriate embedding dimension is always an open and challenging problem for deep learning. In NLP, motivated by the unitaryinvariance of word embedding, [Yin and Shen, 2018] proposed the pairwise inner product loss to measure the dissimilarities between word embeddings. Inspired by the this work, [Wang, 2019] proposed a fast and reliable method based on Principle Components Analysis (PCA) to choose the dimension of word embedding, which use grid search to reduce the complexity of the algorithm. By rethinking the classical skip-gram algorithm, [Hung and Yamanishi, 2020] proposed a novel information criteria-based method to select the dimension of word embedding, and gave a theoretical analysis from the perspective of probability theory. Similarly, in Computer Vision (CV), researchers also try to reduce the representation dimensionality by sampling operation on the input data [Luo et al., 2020]. In graph mining, existing work about embedding dimension selection is based on dimensionality reduction to select important features. Many previous dimensionality reduction algorithms are based on a predefined graph, however, there are noise and redundant information in original data. [Xiong et al., 2017] proposed the linear manifold regularization with adaptive graph to directly incorporate the graph construction into the objective function to solve the problem. Similarly, [Liu et al., 2020] proposed the termed discriminative sparse embedding to learn a sparse weight matrix to reduce the effects of redundant information and noise of original data. In order to avoid choosing the dimension that is outliers, [Zhu et al., 2018] proposed a robust graph dimensionality reduction algorithm to map high-dimension data into lower-dimensional intrinsic space by a transformation matrix. Although there are amounts of fantastic work for dimension selection. However, these methods focus on studying how to choose important features to reduce the dimensionality instead of direct selection based on the graph. Moreover, these methods ignore the rich link structures of graph data in dimensionality reduction, which results in loss of information.

1 https://github.com/RingBDStack/MinGE

Structure Entropy. The conception of structure entropy originate from the research of [Shannon, 1953], who establish the structural theory of information to support the analysis of communication system. Subsequently, a large number of methods are proposed about understanding the complexity of networks. [Mowshowitz and Dehmer, 2012] proposed the entropy of graph to measure the entropy of the distribution p(G) at the global level. Besides, there were some methods to measure the structure entropy of nodes. [Raychaudhury et al., 1984] first proposed the local measure of graph entropy, which is distance-based. Some extension works such as parametric graph entropy [Dehmer, 2008], Gibbs entropy [Bianconi, 2009], Shannon entropy, and Von Neumann entropy [Braunstein et al., 2006] designed the structure information measurement of the network from different angles. Furthermore, [Li and Pan, 2016] first proposed the metric for structure information and defined the K-dimensional structure information of the graph, which can not only detect the natural or true structure but also can measure the complexity of dynamic evolving networks.

So far, there is still no effective solution to directly select an appropriate node embedding dimension for any given graph. Therefore, in this paper, we revisit the NEDS from the perspective of minimum entropy principle. Based on it, we design a novel MinGE algorithm that contains feature entropy and structure entropy for direct NEDS.

3 Methodology

In this section, we first introduce the basic notations used in this paper. Then we present the overall framework of our minimum graph entropy approach MinGE, followed by the detail of how to calculate the feature entropy and the structure entropy for graph data with rich link structures.

3.1 Notation

Suppose we are given an undirected graph G = (V,E,A), where V denotes the node set of the graph, E denotes the set of edges, and A ∈ RN×N denotes the adjacency matrix with the element A[i, j] = A[j, i] indicating whether edge (vi, vj) in E. N is the number of nodes. The link structures can be presented by the first-order adjacency matrix A and the second-order adjacency matrix A2 . The adjacency matrix after normalization is denoted as Ar. Similarly, the secondorder adjacency matrix after normalization is denote as A2r . The degrees of all nodes are represented by a vector D ∈ R1×N , and the normalized degree is Dr.

3.2 Graph Entropy

Information entropy proposed by Shannon [Shannon, 1948] is a measure of information uncertainty, which is defined as:

where H denotes the entropy, Pi is the probability of event i, n is the number of events. It indicates that, the smaller the entropy, the lower information uncertainty, which equally means the more useful information. However, using single information entropy to measure graph data with rich link structures is brittle. Therefore, in this paper, we propose a novel graph entropy to consider both rich node features and link structures on graphs, which is defined as:

where Hg represents graph entropy, Hf and Hs represents feature entropy and structure entropy respectively. λ is a hyperparameter that controls the ratio of structure entropy for NEDS. In the following, we will discuss how to define Hf and Hs in detail. Especially for the feature entropy Hf , it establishes the connection between dimension n and graph entropy. The structure entropy further search the ideal node embedding dimension. Finally, we can directly calculate the appropriate node embedding dimension n by setting Hg = 0.

Feature Entropy. Information entropymeasures the uncertainty of information. The core of information entropy is how to define the basic unit of events. For graph data, we design a novel feature entropy as shown in Fig. 1. Based on the assumption that the node embeddings of adjacent nodes to be more similar, we use node embedding dot product of node pairs as the basic unit and the probability is defined as:

where vi and vj are the corresponding node embedding, 〈·, ·〉 is the dot product operation. For brevity, we denote Z = ∑i,j e〈vi,vj〉 . The feature entropy of graph data is defined as:

To calculate Eq. (4), we approximate the sum operation with sampling, which is defined as:

where E is the expectation operation. Plugging the approximate expressions from Eqs. (5) and (6) into Eq. (4), we can calculate the feature entropy by

However, 〈vi, vj〉 is hard to calculate directly in Eq. (7). In the experiments of graph representation learning, we observe that the absolute value distribution of the values of each dimension is uniform. Therefore, we assume that the absolute value of each element is 1, which is called the distributed hypothesis [Sahlgren, 2008]. Furthermore, to calculate 〈vi, vj〉, we map node embeddings to the n-dimensional hyper-sphere with radius √n. Then, 〈vi, vj〉 = n ∗ cosθ [Li et al., 2020], where θ is the angle between any two vectors, and it connects the node embedding dimension n with entropy. Next, the probability distribution of the angle θ between two random vectors in the n-dimensional hyper-sphere is needed to keep n as the only variable. Because of the isotropy, we only need to consider the unit vector. Besides, we only need to fix one of the vectors and consider the random change of the other vector. Therefore, we set the n-dimensional random vector x = (x1, x2, · · · , xn), the fixed vector is y = (1, 0, · · · , 0). Converting x to hyper-sphere coordinates is defined as:

where r = √x21 + x22 + · · · + x2n = 1 is a radial coordinate, ϕn-1 ∈ [0, 2π), others ϕ ∈ [0, π]. Note that ‖x‖ = 1 and ‖y‖ = 1, therefore the angle between x and y is

where arccos is the inverse cosine (arccosine) function. Eq. (9) shows that the angle between x and y is ϕ1. In particular, the probability of the angle between x and y that does not exceed θ is

The probability density of θ is denoted (following [Henderson and Moura, 1996]) by

Therefore, plugging the probability density from Eq. (11) to Eq. (7), the feature entropy is updated by

where the calculation of the expectation operation is

Structure Entropy. Structure entropy measures the complexity of networks, which is original from the Shannon's 1953 question [Jr., 2003]. For graph data, we design a novel structure entropy to measure the information of link structures as shown in Fig. 1. The structure entropy uses normalized node degree as basic unit to further search the ideal dimension, which considers two-hop neighbors. First, given a graph with the adjacency matrix A that contains first-order link structures, the second-order adjacency matrix is defined as A2 = AT A to measure the second-order link structures. At the same time, the degree vector D is generated by the adjacency matrix A. Second, the normalized degree vector Dr, which contains first-order and second-order link structures, can be defined as:

where A2r represents the normalized second-order adjacency matrix defined as:

where A2 [i, j] is the value of the i-th row and j-th column of the second-order adjacency matrix A2 . Following the paradigm of information entropy, the structure entropy with the normalized degree of nodes as a unit event is defined as:

where Dr[i], calculated by Eq. (14), is the normalized degree of node i. Therefore, the graph entropy is defined as:

Algorithm 1: MinGE

Input: Graph G(V, E, A); Hyperparameter λ;

Output: The ideal node embedding dimension n for the graph G

1 Initialize A2 ←- AT A;

• 2 Calculate A2r ←- Eq. (16);
• 3 Estimate the feature Entropy by Hf ←- Eq. (7);

4 Calculate Dr ←- Eq. (15);

• 5 Calculate the structure entropy by Hs ←- Eq. (17);
• 6 Calculate the graph entropy by Hg ←- Eq. (18);
• 7 Obtain the ideal node embedding dimension
• n ←- Hg = 0.

Algorithm. We summarize the whole process of MinGE in Algorithm 1. To be specific, we first perform sampling to approximate the sum operation and map the node embedding to the n-dimensional hyper-sphere with radius √n to estimate the feature entropy Hf by Eq. (7) and (12). Then we calculate the structure entropy Hs by Eq. (17) based on the normalized degree vector in Eq. (15). Finally, according to the minimum entropy principle [Zhu et al., 1997], we can get the ideal node embedding dimension n by setting Hg = 0. The calculated dimension n is taken as the ideal embedding dimension that can carry all information of node features and link structures.

Time complexity analysis. In theory the time complexity of MinGE is O(n2 ), due to matrix multiplication. However, graphs are usually sparse in practice, and we optimize MinGE with sparse matrix computations, which results in rather efficient computation much less than O(n2 ) in practice (as analyzed in Fig. 3).

4 Experiments

In this section, we conduct extensive experiments on benchmark datasets to demonstrate the effectiveness and generalizability of the proposed MinGE for GNN methods.

4.1 Experimental Settings

Datasets. In our experiments, we choose the most authoritative benchmark datasets, Cora, Citeseer, Pubmed proposed by [Sen et al., 2008] and Airport [Chami et al., 2019]. More details of the datasets are shown in Table 1. We conduct node classification and link prediction on above benchmark datasets, and evaluate the performance of our MinGE.

GNNs. We validate the effectiveness and generalizability of MinGE on most popular models, including Multi-Layer Perception (MLP), Graph Convolution Network (GCN) [Kipf and Welling, 2017], Graph Attention network (GAT) [Velickovic et al., 2018] and Graph Convolution Network via Initial residual and Identity mapping (GCNII) [Chen et al., 2020].

Protocols. For node classification task, following the experiment setting of GAT [Velickovic et al., 2018], only 20 samples per class are allowed for training. We further choose 80, 140 per class for Cora, Citeseer and Airport, and 2000, 3000 per class for Pubmed to crop the data set at different scales and postpone the index to divide the validation set with 500 and a test set with 1000. For link prediction task, we randomly split the edges with a ratio of 85%, 5%, and 10% for training, validation and test sets. For both tasks, comparative experiments are constructed by setting dimension interval to 20 for GNNs. Early stopping strategy is used on validation set with a patience of 100 epoches for all experiments. All results are the average of 10 times. Furthermore, experiments are conducted to validate the efficiency of MinGE.

Hyperparameters. MinGE has only one hyperparameter λ to control the ratio of the structure entropy. We set λ = 1 in experiments and analysis it in Section 4.2. The values of node embedding dimension calculated by the MinGE algorithm are 98, 101, 123, 100 for Cora, Citeseer, Pubmed and Airport separately. Where these dimensions are the size of the last layer of GNNs representation model. In practice, we set hidden as a hyperparemeter to control the dimension size.

For other hyperparameters, we follow the settings in the original text for most models, which are considered to be optimal. However, because of the differences between the datasets, we also make corresponding adjustments. For the MLP model, the optimizer is Adam with learning rate is 0.01 and weight decay is 0.0005, epoch is 250, drop out is 0.5. For GAT and GCN models, we fully keep the default settings. For GCNII model, the hyperparameters partly follow the default settings and early stopping strategy. The differences are that the learning rate is 0.008 for Cora, the lamda is 0.3 for Citeseer, the dropout is 0.5 and lamda is 0.4 for pubmed, and layer is 16 for all datasets.

4.2 Results and Analysis

Performance on node classification and link prediction. For node classification and link prediction tasks, the results of GNNs with different dimensions on benchmark datasets are shown in Table 2. Where Apt denotes the appropriate dimension calculated by the MinGE in all Tables. From Table 2, by comparing with other dimensions, we can see that GNNs with the appropriate dimension selected from MinGE achieve the best or near the best performance. Besides, from the perspective of overall trend, we can see that it always locates in the peak area of the result change curve. Moreover, we also compare with the experimental results of GCN, GAT, GCNII models in the original texts. We find that GNNs with MinGE can improve 2%, 1.3%, 1.6% on Cora and 0.6%, 0.6%, 0.2% on Pubmed respectively. The above experimental results verify the effectiveness and generalizability of MinGE in guiding the NEDS for GNNs on different tasks and GNN models. The main reason is that around an appropriate dimension for a GNN model, the lower node embedding dimension is hard to cover all information due to the limitation of expression capacity, and the higher one tends to overfit the training data due to the excessive model complexity. In order to search an appropriate dimension for each model of each task, MinGE leverages the both feature entropy and structure entropy to measure the node features and link structures in the graph for NEDS, which leads to better performance.

Furthermore, in order to eliminate the influence of uneven data distribution and further verify the genralizability of MinGE, we conduct experiments on benchmark datasets cropped at different scales. The performance of GNNs with 80, 140 samples per class for Cora, Citeseer and Airport separately and 2000, 3000 samples per class for Pubmed are shown in Fig. 2. Where Apt denotes the ideal dimension selected by MinGE, and Def denotes the default dimension mentioned in original paper. According to the results, it is obvious that the performance of GNNs with the appropriate dimension selected by MinGE always locate in the peak center of the accuracy curves, and the accuracy of each model has been greatly improved as the training set increases. Furthermore, compared with GNNs with default dimension, GNNs with the ideal dimension all achieve better performance. The experimental results are in line with the conclusions verified in Table 2, which indicates generalizability of MinGE.

Memory Efficiency. GCNII is the current state-of-the-art model that can achieve better performance with deeper neural networks, as shown in Table 3. However, deeper network spends more memory and time during model training. Compared with the node dimension by default in original paper, MinGE can find an appropriate dimension for GCNII with different numbers of layers. In such a case, GCNII with MinGE can use fewer layers but achieve similar or better performance to a deeper GCNII with the node dimension by default setting. For example, the performance of GCNII with 16 layers and the node dimension by default is worse than GCNII with two layers and an appropriate dimension selected by MinGE on Citeseer. In summary, by using MinGE, GCNII can choose fewer layers to achieve good performance while memory limitation becomes crucial.

Time Efficiency. Considering fairness, we conduct experiments to compare the time that MinGE runs once with that GNNs run once. Fig. 3 shows the running time of MinGE and GNN methods. From these results, we can observe that MinGE costs much less runtime compared with training GNNs. It turns out our approach adds almost no additional computational overhead and is more efficient for an appropriate embedding dimension selection through MinGE. Note that, our approach only requires the runtime of MinGE with a single execution of different GNNs here, while finding a good dimension by grid search needs to run the GNNs multiple times, so as to cost more computational burden and time.

HyperparameterAnalysis. In ourMinGE algorithm, there is only one hyperparameter λ, which controls the weight of structure entropy. The structure entropy provides additional help to the feature entropy. In order to determine the weight of the strcture entorpy, we use GCN to analyze λ on benchmark datasets. All dimensions calculated by MinGE

Dataset are rounded up. From Table 4, it is not hard to see that the structure entropy is often equally important as the feature entropy for NEDS in general. Therefore, we can simply set λ to 1 by default given an arbitrary graph. We also observe that the graph entropy with λ = 0.1, which can be considered as feature entropy alone, can give pretty good results. Adding structure entropy with different weights can further improve the performance but with slight variance compared with experimental results as shown in Table 2.

5 Conclusion

In this paper, we revisit Node Embedding Dimension Selection (NEDS) for graph data from the perspective of minimum entropy principle. We proposed MinGE, a novel algorithm that combines well-designed feature entropy and structure entropy, to guide the NEDS for GNNs and addressed the challenge of how to directly select the appropriate node embedding dimension for graph data. We focused on MinGE that can maximize node information and structure information for appropriate NEDS by using minimum entropy principle. Moreover, to the best of our knowledge, MinGE is the first study that applies minimum entropy theory to NEDS of graph data. In practice, with this theory, we discovered the effectiveness and generalizability of our MinGE algorithm for popular GNNs. All of our discoveries were concretely validated on benchmark datasets.

Acknowledgements

The corresponding author is Jianxin Li. This work was supported by the NSFC program (No. U20B2053 and 62002007), S&T Program of Hebei through grant 20310101D, and SKLSDE-2020ZX-12. Lifang He is supported by NSF ONR N00014-18-1-2009 and NSFC of Guangdong Province under grant 2017A030313339. Philip S. Yu is supported by NSF under grants III-1763325, III1909323, and SaTC-1930941.