Discrete Network Embedding

1 Introduction

Networks are natural tools to model pairwise relationships and inter-dependence among data in a variety of applications including communication networks, social networks, citation networks, etc. It is well recognized that networks are highly complicated and sparse which impose significant challenges in many network analytic tasks, such as community detection, node classification, and link prediction. For years researchers have made efforts to solve each of these tasks separately until recently network embedding emerged as a general way for many of these problems.

Network embedding aims to transfer the graph representation into continuous feature values, where each node corresponding to a low dimensional vector. The key idea behind is to preserve the structure relationship of the network so that nodes with links are close to each other in the vector space. After learning the new representations, any network analytic tasks can be easily carried out by using off-the-shelf machine learning algorithms based on the new representations. Due to its effectiveness in many tasks, such as graph clustering [Tian et al., 2014], link prediction [Dai et al., 2017], and personalized recommendation [Zhang et al., 2017], network embedding has attracted increasing attention in recent years.

∗ indicates equal contribution.

Network embedding can be roughly categorized into three groups: (1) random walk-based algorithms, (2) matrix factorization-based methods, and (3) deep learning-based approaches. The random walk-based algorithms generate a large number of truncated random paths over a network and preserve the neighborhood relationship of nodes in the paths. By borrowing the idea of word representation in NLP, DeepWalk [Perozzi et al., 2014] becomes the first elegant framework for network embedding in an online manner. Node2Vec [Grover and Leskovec, 2016] further exploits the biased random walks to capture the global structure information. Other methods either learn asymmetric proximity [Zhou et al., 2017] or capture multiple sources of information in the network to learn network embedding [Pan et al., 2016].

Matrix factorization-based aims to decompose a matrix into low dimensional latent factors which can be considered as the new representation of nodes. They vary in the objective functions. Early approaches such as modularity maximization and eigen-decomposition, aim to learn community indicative functions, while TADW [Yang et al., 2015] exploits two-step of the transition probability matrix via inductive matrix factorization. Recently, it has been proven in [Qiu et al., 2018] that many approaches, including LINE [Tang et al., 2015b], PTE [Tang et al., 2015a], DeepWalk and Node2Vec, are equivalent to matrix factorization methods. Recently, deep learning approaches [Cao et al., 2016; Wang et al., 2016] have been proposed to learn non-linear representations for nodes.

Despite the success of current network embedding approaches, the network embedding is learned in a continuous space, which in practice imposes severe challenges in the storage and computation cost, particular on large-scale datasets. Therefore, it is imperative to develop a compact network embedding framework, which has been less well studied and remains a very challenging area.

Binary code learning [Wang et al., 2018] has gained increased interests in many large-scale applications. It encodes the original high-dimensional data into a set of short binary codes with similarity preservation. Thus the calculation and storage in Hamming space are both at very low cost. This triggers us to propose a novel discrete network embedding (DNE). DNE aims to learn the short binary code to represent each node. The advantages of DNE over conventional embedding methods lie in the low cost of computation and storage. As shown in the experiments, DNE reduces the storage of the embedding and model size to 64 times on the three datasets; meanwhile, it dramatically improves the efficiency of training and classification. The overview of the proposed DNE is illustrated in Figure 1. The main contributions of this work are summarized below:

• We propose a novel discrete network embedding (DNE) for compact representations. DNE represents each node using binary codes, which can significantly reduce the computational and storage costs. To the best of our knowledge, DNE is the first work that learns a discrete representation for networks.
• DNE leverages Hamming similarity between two binary embeddings to well approximate the ground-truth similarity. To improve discrimination of embedding, DNE jointly learns the discrete embedding and classifier. The proposed discrete multi-class classifier is able to expedite classification.
• Extensive experiments demonstrate that DNE achieves lower storage and computational complexity than stateof-the-art network embedding methods, while achieving comparable accuracy.

The rest of this paper is arranged as follows. In Sections 2 and 3, we discuss related work and background. Section 4 presents the proposed DNE method. The experiment is outlined in Section 5. The conclusion is drawn in Section 6.

2 RelatedWork

Network Embedding Learning Network embedding has become an effective method for many network analytic tasks, including node classification, clustering, and anomaly detection. Regarding the information they exploit for learning the representation, network embedding can also be distinguished into two groups (1) structure-preserving algorithms, and (2) content augmented algorithms.

Structure-preserving algorithms take in a network as the input and aim to preserve the structure relationship between nodes. While capturing the structure relations, they typically employ random walks [Perozzi et al., 2014; Grover and Leskovec, 2016], matrix factorization [Tang and Liu, 2009; Zhou et al., 2017], or deep learning approaches [Cao et al., 2016; Wang et al., 2016].

Content augmented algorithms assume that the node content is available on each node and aim to embed both network structure and node content into a low dimensional space. These algorithms include TADW [Yang et al., 2015], TriDNR [Pan et al., 2016], DANE [Li et al., 2017], MGAE [Wang et al., 2017], GraphSAGE [Hamilton et al., 2017], and the graph convolutional network (GCN) [Kipf and Welling, 2016], to name a few.

Unfortunately, all these works learn the continuous representations, which impose serious challenges in the storage and computation cost on large-scale datasets. To solve this issue, this work aims to learn a discrete network embedding.

Binary Code Learning Binary coding technique, also known as Hashing [Wang et al., 2018], has become a widelystudied solution to approximate nearest neighbor search, due to its great gains in storage and computation. The basic idea of hashing [Wang et al., 2018; Weiss et al., 2009; Gong et al., 2013; Shen et al., 2017b] is to map highdimensional data into a low-dimensional discrete code space called Hamming space, while preserving similarity structure in the original space. Accordingly, each data point is represented by a short binary code called hash code consisting of a sequence of bits.

Existing hashing methods [Wang et al., 2018] learn binary code from images, texts, videos and retrieval tasks. This work first investigates the binary coding technique in network embedding.

3 Notation and Background

We use bold uppercase, lowercase letters, and italic letters to denote matrices, vectors, and scalars, respectively. For any matrix A, Aij denotes the (i, j)-element of A, and Tr(A) is the trace of A if A is square, A⊤ denotes the transposed matrix of A. Let Im represent the identity matrix in Rm×m. We denote ‖ · ‖F as the Frobenius norm, and sgn(·) : R → {+1,-1} as the round-off function.

Let G = (V,E) be a network with n interconnected nodes and e edges. It can be also represented by the adjacency matrix A ∈ Rn×n , where Aij represents the link information from node i and node j, and it is defined as 0 if there is no edge. The goal is to learn representations of nodes U ∈ Rn×m, where m (m ≪ n) is the dimension of the representation.

Matrix Factorization is a powerful method for network embedding. [Yang et al., 2015; Qiu et al., 2018] reveal that the state-of-the-art DeepWalk is equivalent to matrix factorization. It seeks a basis matrix V ∈ Rn×m and a representation matrix U ∈ Rn×m to well approximate the similarity matrix S. This gives the following objective function

U is viewed as the real-valued representation of nodes, and can be used in many tasks, e.g., node clustering, classification.

In this work, we consider the problem of classifying network nodes into several categories. There are two main drawbacks of existing network embedding techniques in this setting: 1) The storage cost of the real-valued embedding matrix U is expensive. In addition, the computation complexity of classification is prohibitive when the network is large. 2) The learned embedding is not optimal for classification. The learning model, i.e., (1) does not optimize the classification loss, and thus the learned embedding is not discriminative. The following section presents a discrete network embedding to overcome the limitations of existing approaches.

4 Discrete Network Embedding

In this section, we present a discrete network embedding (DNE) which enforces the embedding as binary codes. The proposed model considers both the embedding learning and classification design within a unified framework.

4.1 Formulation

Discrete Matrix Factorization Existing research shows that the state-of-the-art DeepWalk is equivalent to matrix factorization on the similarity matrix S. The (i, j)-element of S is defined as

where ei is an indicator vector, where the i-th element is 1, and the others are 0, At is the multiplication of A by t times. Following [Tu et al., 2016], we set S = A+A2 2 .

We are interested in imposing the binary constraint on the network embedding, i.e., B = [b1, . . . , bn] ∈ {+1,-1}m×n . Specifically, the Hamming similarity between bi and bj is defined as

where 1(·) denotes the indicator function that returns 1 if the element is true and 0 otherwise. Specifically, sim(i, j) = 0 if all the bits between bi and bj are different and sim(i, j) = 1 if all the bits are the same.

We use the inner product of binary network embedding to well reconstruct the similarity matrix S. This leads to the following discrete matrix factorization objective function:

where we enforce two additional constraints on B: the bit uncorrelated constraint remove the redundancy among the bits; the bit balanced constraint splits the dataset as balanced as possible in each bit.

Discrete Multi-class Classifier We focus the multi-class classification problem in this work, while the setting can be easily extended to multi-label classification. In addition, the labels of a subset of nodes, i.e., T = {(b1, c1), · · · , (bl, cl)} are given for training the classifier. We assume that the classifier is linear and parameterized with the weight matrix W = [w1, · · · ,wC], where C is the number of the classes. For any embedding b, it is classified according to the maximum of the score vector

Particularly, we further impose the binary constraint on weight matrix, i.e., wc ∈ {+1,-1}m (c = 1, . . . ,C). The binary constraint reduces the classification model size [Shen et al., 2017a]. In addition, due to the binary nature of b and wc, the inner product w⊤ c b can be efficiently computed. The classification efficiency can be greatly improved. Moreover, we propose a simple yet effective loss function for multi-class classification. Let bi be the embedding of the i-th node, and belong to class ci. Ideally, we expect the large inner product on wci , and small inner products on wc, c ̸= ci, such that the classification error can be minimized. Formally, the multi-class classification loss function can be defined as

Note that we use the simplest linear loss in this work, and other losses, such as square loss, hingle loss, and exponential loss can be also explored in our proposed framework.

Joint Learning Framework We have introduced the discrete network embedding and classification models. Next, we propose to learn a classification-oriented network embedding, such that the learned embedding is optimal for the classification task. To this end, we propose to jointly learn the embedding and classification within a unified framework, which leads to the following objective function

where λ is a nonnegative parameter to balance embedding and classifier learning. In the next section, we propose a computationally tractable optimization algorithm to solve (7).

4.2 Optimization

In essence, (7) is a nonlinear mixed-integer optimization problem involving the discrete constraint on B, W and nonconvex orthogonal constraint on B, which is generally NPhard problem. We propose a tractable alternating algorithm to iteratively optimize each variable. The flowchart of DNE is described in Algorithm 1.

Embedding Learning GivenW, we solve the sub-problem with respect to B. We first rewritten (6) into a compact matrix form, i.e., Tr(Wo⊤B), where the i-th column of matrixWo with size m × n is defined as wo i = ∑Cc=1 wc -Cwci . Due to the fact that BB⊤ = nIm, the sub-problemwith respect to B can be rewritten as

We further transform the uncorrelated and balanced constraints into two regularization terms. With the fact ‖BB⊤ - nIm‖2F = ‖BB⊤‖2F + const, we have

where µ and ρ are two nonnegative regularization parameters. (9) is challenging due to the discrete constraint, and has no closed-form solution. Inspired by the recent advance in nonconvex optimization, we propose to optimize (9) with proximal gradient method. The main idea is to iteratively optimize a surrogate function. In specific, we iteratively optimize a local function ˆ Li(B) that linearizes L(B) at the point B(i) , and employ ˆ Li(B) as a surrogate of L(B). Given B(i) , the next discrete point B(i+1) can be derived by optimizing the following objective function

where τ > 0 is a constant, ∇L(B(i) ) = -B(i)S + λWo + µB(i)B(i)⊤B(i) + ρB(i)11⊤. Then the updating rule for B(i+1) can be defined as

Note that the function C (x, y) = {x, x ̸= 0 y, x = 0 , C is applied in an element-wise manner in (11) to eliminate the zero entries.

Classifier Learning Given B, we solve the sub-problem with respect toW, i.e., (6). We iteratively optimize the pro-

Algorithm 1 Discrete Network Embedding

Input: Network: G(V,E), embedding dimensionality: m, the label of the training subset T , parameter: λ, µ, ρ, iteration number: Tin, Tout.

Output: embedding: B, classifier: W.

• 1: InitializeWand B randomly.
• 2: repeat
• 3: for i = 1 → Tin do ▷ Embedding Learning 4: Update the embedding B via (11);
• 5: end for
• 6: for c = 1 → C do 7:
• ▷ Classifier Learning
• Update the weight vector wc via (13);
• 8: end for
• 9: until converge or reach maximum iterations

jection weight of each class. The objective function with respect to wc can be reduced to

Clearly, (12) has the optimal solution

4.3 Complexity Analysis

The computational complexity of training the proposed DNE consists of the following two parts. For the embedding learning, calculating the gradient of B requires O(ιm + m2n), where ι = nnz(S), nnz denotes the number of non-zeros. Updating B requires O(Tin(ιm+m2n)), where Tin is the number of iterations. For the classifier learning, updatingW requires O(lmC). Suppose that the algorithm takes Tout iterations to convergence. The overall complexity of DNE is O (Tout(Tin(ιm+m2n) + lmC)). In practice, Tin, ι, m, and Tout are usually small, thus training DNE is fast. Given a new binary embedding b, the classification reduces to retrieve its nearest neighbor from {wc}Cc=1 . The search is very fast via bit operations. The computational complexity of classification in DNE is faster than existing embedding methods, which require O(mC).

In terms of space complexity, DNE needs to store the network embedding B and the weight matrix W, which count for the storage of O(mn) bits and O(mC) bits, respectively. The existing network embedding methods, e.g., DeepWalk, need to store O(mn) and O(mC) real-valued numbers. Therefore, DNE has lower space complexity than existing network embedding methods.

5 Experiments

In this section, we evaluate the proposed discrete network embedding (DNE) on multi-class node classification tasks. All the computations reported in this study are performed on a Ubuntu 64-Bit Linux workstation with 24-core Intel Xeon CPU E5-2620 2.10 GHz and 128 GB memory.

5.1 Datasets

We conduct experiments on three datasets, whose details are as follows.

• DBLP 1 : is a citation network in computer science. Each paper may cite or be cited by other papers, which naturally forms a citation network. In this experiment, the citation network is collected from 4 research areas, e.g., database, data mining, artificial intelligent and computer vision. It consists of 60,744 papers (nodes), 52,890 edges in total, and each node is associated with its title information.
• YOUTUBE 2 : is a social network of Youtube users. It contains 1,157,827 nodes and 4,945,382 edges. The labels represent groups of users who enjoy common video genres.
• FLICKR2 : is a social network of Flickr users. It contains 80,513 users from a photo sharing website and 5,899,882 friendships between them. The labels represent the group membership of users. The network has 195 labels and a user may have multiple labels.

For constructing multi-class datasets, we remove the nodes that have multiple labels in YOUTUBE and FLICKR datasets. In addition, the isolated nodes are removed in the three datasets.

5.2 ComparisonMethods

To demonstrate the effectiveness of the proposed DNE, we compare it with five state-of-the-art network embedding methods. The details of these methods are given below.

• DeepWalk [Perozzi et al., 2014]: DeepWalk performs random walks over networks and employs Skip-Gram model to learn node embeddings.
• DWMF [Yang et al., 2015]: DeepWalk has been shown to be equivalent to matrix factorization [Yang et al., 2015; Qiu et al., 2018]. DWMF is trained on the similarity matrix (A+A2 )/2 to obtain node representation.
• LINE [Tang et al., 2015b]: LINE is the embedding method for large-scale networks. We employ the second-order proximity LINE (2nd-LINE) to learn representations.

1 http://arnetminer.org/citation

2 http://socialnetworks.mpi-sws.org/data-imc2007.html

• Node2Vec [Grover and Leskovec, 2016]: Node2Vec is a biased random walk algorithm based on DeepWalk to efficiently explore neighborhood architecture.
• MMDW [Tu et al., 2016]: Max-Margin DeepWalk (MMDW) is a discriminative network embedding model that obtains discrimination characteristic via the maxmargin classifier.

5.3 Experiment Setup

In this work, we set the dimension of network embedding as 128 for all the methods for fair comparison. For DeepWalk, window size, walk length, and walks per node are set as 10, 40, 40, respectively. For LINE, the number of negative samples is set to 5. For Node2Vec, window size, walk length and walks per node are set the same with DeepWalk, and return parameter p and in-out parameter q are set as 1 and 2, respectively. For the proposed DNE, µ and ρ are set as 0.01, 0.01, and 0.5, respectively; τ and λ are selected from the range of [1, 10] and [0, 1] by cross validation respectively.

For node classification, the representations for the nodes are first obtained from the network embedding methods and then used as features to train a classifier. We randomly sample a portion of the labeled nodes for training classifier and the rest nodes are used for testing. The training ratio increases from 10% to 90% for the three datasets. For DeepWalk, DWMF, LINE, and Node2Vec, the multi-class SVM by Crammer and Singer [Crammer and Singer, 2001] is employed as the classifier, which is implemented by LIBLINEAR package [Fan et al., 2008]. For MMDW and DNE, the classifiers are learned on labeled nodes only and they are jointly learned with network embedding.

5.4 Results

Accuracy Figure 2 shows the accuracy results of all the methods on three datasets. We find some interesting points:

• As training ratio increases, the accuracies of all the methods generally rise.
• Among the comparisons, MMDW has the best performance due to its discrimination, but it is slower than other methods. DWMF outperforms DeepWalk on YOUTUBE, and DeepWalk outperforms DWMF on DBLP and FLICKR.
• The proposed DNE generally has comparable accuracy with the comparison methods. DNE is better than most unsupervised embedding methods in some cases of large training ratios. It reveals that the discrete embedding obtains high discrimination as DNE jointly learns the embedding and classifier.

Time Table 1 shows the training time of all the methods on three datasets. It includes the time of learning embedding and classifier. As can seen from this table, the proposed DNE is the fastest method among all the baselines. For example, DNE is 46 and 116 times faster than DeepWalk and MMDW, respectively. LINE takes the second place, which is followed by DWMF, DeepWalk, and Node2Vec. MMDW is the slowest among all the methods. The results verify our computational analysis.

In addition, we evaluate the classification efficiency. The time of classification for the comparison methods are quite close, thus we only compare DeepWalk and DNE. Table 2 reports the time of classification for DeepWalk and DNE. As can be seen, DNE is clearly faster than DeepWalk for around 2 times among all the cases, which also verifies our complexity analysis and motivation. DNE uses a discrete classifier via binary code. The classification is calculated in the Hamming metric, which is more efficient than the conventional Euclidean calculation in DeepWalk.

Memory Usage Table 3 reports the memory usage of DeepWalk and DNE for the storage of network embedding. We clearly observe that compared with DeepWalk, DNE significantly reduces the memory storage of embedding for 64 times within the same dimension. DNE only needs to store less than 1M of binary codes to represent the three datasets, even for the large-scale FLICKR dataset. In addition, the model sizes of classifiers in DeepWalk and DNE are shown in Table 2. Due to the discrete representation of classifier, we see that the model sizes of DNE are much smaller than those of DeepWalk. These results imply that DNE can work well in some extreme scenarios, e.g., resource-scarce devices.

Parameter Analysis We study the sensitivity of the key parameter, i.e., λ, in our proposed DNE. The training ratio is fixed as 0.5, and λ is ranged between [0, 1] with a step of 0.1, and classification accuracy with respect to different λ is shown in Figure 3. From Figure 3, we observe that the classification accuracy improves as λ increases from 0, and remains stable after λ reaches to around 0.2. It shows that the good performance can be achieved from the wide range between [0.2, 1]. The parameter analysis reveals that the joint learning of classifier indeed enhances the discrimination of the discrete embedding.

6 Conclusion

This work focuses on the challenging problem of seeking compact representation for network embedding. We propose a novel discrete network embedding (DNE) that leverages short binary codes to represent each node. A discrete multiclass classifier is jointly learned to improve the discrimination of embedding. Compared to existing network embedding methods, DNE enjoys both computational and memory efficiency. Extensive experiments on node classification demonstrate DNE exhibits lower storage and computational complexity than state-of-the-art network embedding methods, while achieving satisfactory accuracy.

Acknowledgments

This research is supported by the National Science Foundation of China (Grant No. 61673220), and partially supported under the Data Science and Artificial Intelligence Center (DSAIR) at the Nanyang Technological University.