Low-Bit Quantization for Attributed Network Representation Learning

1 Introduction

Attributed networks are popularly used to describe a large body of networks where both node links and attributes are obtainable for analysis [Le and Lauw, 2014]. To discover latent patterns from attributed networks, attributed network representation learning or attributed network embedding models are proposed to jointly learn node representations from both node links and attributes. For example, the work [Yang et al., 2015] uses textual attributes to supervise random walks on networks and derives the Text-associated DeepWalk (TADW) model. AANE [Huang et al., 2017a] uses node links to supervise the factorization of attributed proximity matrices. LANE [Huang et al., 2017b] mutually uses node links and attributes as labels to supervise the learning from each other. However, these attributed network embedding models are developed in continuous Euclidean spaces, where the learned representation vectors usually contain redundant information that degenerates computation efficiency and increases storage cost, especially when networks are large.

To reduce the size of network representation and speed up the inference on a big network, considerable efforts have been put on generating succinct network representation with lowbit representations. A pioneer work [Shen et al., 2018b] is to learn binary graph embedding where a short binary code is learnt for each node through factorizing the graph similarity matrix by imposing the Hamming similarity constraint on each pair of nodes. Based on this work, a binary attributed network embedding method [Yang et al., 2018] is proposed that extends the binary network embedding to binary attributed network embedding, where a new WeisfeilerLehman proximity matrix is used to capture data dependence between node links and attributes and a new WeisfilerLehman matrix factorization learning function is proposed by adding an extra binary node representation constraint.

Despite the success of reducing network representation size, the strict binary representation constraint imposed on the learning function often suffer from uncontrollable accuracy loss on test sets. For example, the binary attributed network embedding [Yang et al., 2018] method, by adding the binary node representation constraint on the Weisfiler-Lehman matrix factorization, the node representation on the test set of Citeseer drops at least 2% compared with its real-valued variants without the binary constraint, especially when there are plenty of training examples. Based on the observation, it is natural to raise the question: how to design a compact yet flexible attributed network representation model that can balance representation accuracy and representation size ?

On the other hand, from the perspective of low-bit quantization for convolutional neural networks, there has been a series of methods [Wang et al., 2017] proposed to reduce the size of network parameters while preserving high prediction accuracy. Low-bit compression of deep neural networks such as training binary neural networks with weights constrained to +1 and -1 [Courbariaux et al., 2016], ternary networks [Zhu et al., 2016] and extremely low-bit neural networks [Leng et al., 2017] have been popularly studied recently. Compared to full-precision models, these compressed models are sparse and much smaller, which can potentially be accelerated with customized circuits and deployed to mobile devices. In particular, the early work [Denil et al., 2013] pointed out that network weights have a significant redundancy, and proposed to reduce the number of parameters by exploiting the linear structure of network, which motivated a line of low-rank matrix and tensor factorization based compression algorithms. The achievement in low-rank matrix and tensor factorization based compression motivates to learn low-bit quantization for attributed network embedding based on matrix factorization.

In this paper, we study the problem of flexible and compact attributed network representation and present a new Low-Bit Quantization for Attributed Network Representation Learning model (LQANR for short). Specifically, we use a k-hop proximity matrix to capture data dependence by propagating node attribute information from k-layer neighboring nodes to a given target node. Based on the k-hop proximity matrix, we formulate a new matrix factorization function to learn the low-bit node representation, where the weights of different layers of neighboring nodes are learnable instead of manually setting. The learning function falls into the category of mixed integer optimization and we propose an efficient mixed-integer based alternating direction method of multipliers (ADMM) algorithm for solution. Experimental results on real-world datasets validate the performance of the proposed LQANR method. The framework of LQANR is illustrated in Figure 1. The contribution can be summarized as follows,

• We first study the low-bit attributed network embedding problem and present a new LQANR model as the solution. LQANR can learn compact representation with stably high accuracy.
• We propose a new mixed-integer based alternating direction method of multipliers (ADMM) algorithm to efficiently learn the low-bit node representation and the layer-wise aggregation weights.
• We conduct experiments to validate the performance of the proposed LQANR model.

2 RelatedWork

Attributed network embedding. Current network embedding methods can be categorized into plain network embedding [Yan et al., 2007] and attributed network embedding [Chang et al., 2015]. Different from plain network embedding that independently vectorizes node links without using auxiliary information from node attributes, attributed network embedding jointly models their dependence, by using node attributes as class labels to supervise the learning of node links, or vice versa. A typical attributed network embedding model is the TADWmodel [Yang et al., 2015] that uses textual attributes to supervise random walks on networks. Similar works include AANE [Huang et al., 2017a], LANE [Huang et al., 2017b], and DANE model [Li et al., 2017].

Low-bit quantization for compression. Quantization methods including hashing are used to encode real-valued data to low-bit discrete data while preserving similarity structure in the original space [Wang et al., 2017]. The low-bit codes can facilitate to represent and search of massive data because it only needs about one hundred bits to represent one data item, and computation in Hamming space is efficient by using the bit operations. Most Hashing methods use one single bit -1/+1 to quantize each projected dimension, such as the spectral hashing [Liu et al., 2014], supervised discrete hashing [Shen et al., 2015] and deep learning based hashing methods [Shen et al., 2018a]. There are also works quantizing real-valued data to multiple-bit codes using Hashing method, such as double bit quantization[Kong and Li, 2012], q-bit Manhattan quantization [Kong et al., 2012] and Variable Bit Quantization [Moran et al., 2013]. Recently discrete network embedding approach is proposed to learn binary codes for plain network [Shen et al., 2018b], and randomized hashing method [Wu et al., 2018] and binarized network embedding [Yang et al., 2018] are proposed for compressing embedding for attributed networks. In this paper, we learn compact low-bit codes for attributed network embedding.

Graph signal processing. Graph signal processing [Sandryhaila and Moura, 2013] extends the signals and filters in traditional time and image based signal processing to irregular graph domains. In the spatial domain, smooth graph signals denote that neighboring nodes tend to have similar values. In the spectral domain, the smoothness of graph signals are typically called bandlimitedness. To create graph filters, functions of graph-shift operators or adjacency matrices are based on either rules or learning functions. The polynomial form of adjacency and the Laplacian matrix are used as graph filters, due to the capability of capturing local structure of graphs and ease of implementation [Ortega et al., 2018].

3 Problem Statement

An attributed network can be represented as G = {V, E, X}, where V = {vi}ni=1 denotes nodes, E = {eij}ni,j=1 denotes undirected edges, and X = {xi}ni=1 ∈ Rn×f denotes attribute vectors of the nodes with f the dimension of attribute vectors. In addition, the structure of G can be derived from edges in E, denoted as an adjacency matrix A, where Aij = 1, if eij ∈ E; otherwise, Aij = 0. By adding a selfloop to each node in the network, we have ˜ A = A + I , where I is an identity matrix. ˜D = diag( ˜ d1, ..., ˜ dn) is a degree matrix of ˜ A, with ˜ di = ∑j ˜aij being the degree of node vi.

Given an existing attributed network G, we need to embed each node vi ∈ V into a d-dimensional low-bit vector bi ∈ {-2N , ...,-21 ,-1, 0, 1, ...,-2N }d , where N is an integer which determines the bit-width. bi is the ith row of matrix B ∈ Rn×d . matrix B should preserve the structure information A and the attribute information X in G.

How to design a proximity matrix that can jointly describe structure A and attribute X is the most important question. This can be considered as a problem of designing a graph signal processing filter [Sandryhaila and Moura, 2013]. We consider attribute X as the graph input signal on each node and use graph adjacency matrix to create a k-hop graph filter. Then, a proximity matrix Pk is generated as the output signal. Different k-hop matrix Pk captures different layer-wise information from the neighboring nodes. We can learn the weights of Pk based on the specific applications.

Concretely, given a network G with adjacency matrix A and attribute matrix X, let ˜D be a degree matrix of ˜ A, the k-hop proximity matrix Pk is defined as Pk = ( ˜D-1 ˜ A)kX, where k is the number of aggregation layers.

4 The LQANRMethod

In this section, we first formulate the learning function of Low-Bit Quantization for Attributed Network Representation Learning model (LQANR) based on matrix factorization under the low-bit quantization constraint. Then, we propose an efficient mixed-integer based alternating direction method of multipliers algorithm as the solution.

4.1 Formulation

Given a target node, the k-hop proximity matrix Pk aggregates attribute and structure information from its k-layer neighboring nodes. Then, Pk can be factorized to generate a low-dimensional representation of the target node. Moreover, considering that neighboring nodes located at different layers contribute differently to the target node, the learning function needs to capture the aggregation importance weights in a layer-wise manner.

The representation learning function can be formulated by simultaneously learning the low-bit node representation and the layer-wise aggregation weights. Assume that αk is the importance weight of matrix Pk, matrix B ∈ Rn×d is the low-bit node representation, matrix Zk ∈ Rd×f is an auxiliary matrix with respect to layer k. Then, the learning problem can be formulated as follows,

where β is a regularization parameter with respect to auxiliary matrices Zk, K is the total number of layers we consider in the model. A large layer number K may cause oversmoothing when learning node attributes, while a small K cannot fully take advantage of network information. Due to the integer constraint over the representation matrix B, Eq.(1) is hard to solve which requires efficient algorithms.

4.2 Optimization

In this part, we present an efficient algorithm to iteratively optimize variables Zk, B and α in Eq.(1). The algorithm updates one parameter at a time and converges very fast.

Given B and α fixed, solve the sub-problem with respect to Zk in Eq.(1). The loss function becomes,

where tr(.) is a trace norm. By calculating the derivative of Eq.(2), we derive a closed form solution as follows,

B-step

It is difficult to solve B due to the discrete constraint. Given Zk and α fixed, rewrite the objective function in Eq. (1) with respect to B as follows,

Due to the discrete constraint, the optimization problem above is NP-hard.

Here, We introduce an auxiliary variable Q to decouple the parameters in the objective and the discrete constraint. The idea is largely motivated by the successful application of ADMM in mixed integer programs [Leng et al., 2017]. Then, the objective function in Eq.(4) can be written as,

where Ic is defined as an indicator function. IC(Q) = 0 if Q ∈ {-2N , ...,-21 ,-20 , 0, 20 , 21 , ..., 2N }; otherwisse, IC(Q) = +∞. The augmented Lagrange of Eq.(5), for parameter ρ > 0, can be formulated as,

Eq.(6) can be solved by repeating the following iterations,

Benefit from the decoupling of ADMM, Eq.(7) is an unconstrained objective function. We can easily calculate the gradient with respect to matrix B,

The closed form solution is given in Eq.(11), where I is an identity matrix.

In order to solve Q, Eq.(6) can be rewritten as,

The optimal solution of Q is

where ∏0,±1,±2,..,±N denotes the projection of (Bt+1 +λt ) with respect to the discrete set. After either the predefined iterations or the convergence of ADMM, Q is assigned to B and the algorithm continues to update α and Zk.

α-Step

Given Zk and B fixed, rewrite the objective function in Eq. (1) with respect to α as follows,

The optimal solution to α in Eq.(14) is αk = 1 corresponding to the minimum ‖Pk - BZk‖2F and αk = 0 otherwise. This solution means that only one order of Pk is finally selected. However, the solution of a single order does not meet our objective on exploring the complementary property of multiple orders to get a better embedding.

Alternatively, we use a trick based on the work [Xia et al., 2010] to avoid the single order solution. We set αrk ← αk with r > 1 and obtain the Lagrange of Eq.(15) as below,

By setting the derivative of L(α, η) with respect to αk and η to zero, we obtain

Algorithm 1 The LQANR model

Input: Structure A, attribute X, dimension d, # of iterations t1 and t2, parameters K, β, ρ, r, N

Output: Low-bit representation matrix B

• 1: Initialize Zk, B, λ randomly
• 2: Repeat until converge or reach t1
• 3: Zk-Step: Calculate Zk using Eq.(3)
• 4: B-Step: Repeat until converge or reach t2 (ADMM)
• 5: Update B using Eq.(10)
• 6: Update Q using Eq.(12)
• 7: Update λ using Eq.(9)
• 8: // After ADMM, let B=Q
• 9: α-Step: Calculate α using Eq.(16)
• 10: return matrix B

Then, αk can be solved as follows,

Because ‖Pk - BZk‖2F ≥ 0, we have αk ≥ 0 naturally. The details of the algorithm is given in Algorithm 1. Empirical studies show that the algorithm takes a few iterations to converge. For example, in our experiments B is iteratively computed and converges around 2 - 10 iterations.

5 Experiments

In this section, we evaluate the performance of LQANR on node classification and link prediction tasks.

5.1 Experimental Setup

Datasets. Three real-world attributed networks are used as testbed. They are popularly used in many network embedding works such as [Yang et al., 2015; Huang et al., 2017b]. We summarize the statistics of datasets in Table 1.

Baseline methods. We compare our method with several popular network embedding methods. DeepWalk [Perozzi et al., 2014] and node2vec [Grover and Leskovec, 2016] use plain network structure for embedding. TADW [Yang et al., 2015], HSCA [Zhang et al., 2016] and LANE [Huang et al., 2017b] use both network structure and attributes. We also compare with the most recent NetHash [Wu et al., 2018] and BANE [Yang et al., 2018] which employs the hashing technique to learn binary network embedding.

Settings and metrics. We set the embedding dimension d = 100 for all baselines. All the parameters are set to be the default values. For node classification experiment, we use SVM [Fan et al., 2008] as the classifier. The training ratios range from 10% to 90% for all the datasets. We use 10-fold cross validation. The performance are evaluated in terms of Micro-F1 and Macro-F1. For link prediction task, we randomly sample 90% neighbors of each node for training and use the rest for testing. We repeat 10 times and evaluate in terms of AUC [Hanley and McNeil, 1982].

5.2 Node Classification Results

The embedding dimension d is set to 100, the bit-width used for each node's representation is {-1, 0,+1}, and the regularization parameter β is set to 0.001. We summarize the results in Table 2 as follows:

• First, LQANR outperforms not only DeepWalk and Node2vec which use pure network structure information, but also the methods which use both network structure and attributes information on Cora, Citeseer and Blogcatalog in terms of Micro-F1 and Macro-F1 under different training ratios. The results validate the effectiveness and robustness of LQANR. The reason is that we use a k-hop proximity matrix to capture data dependence by propagating node attribute information from k-layer neighboring nodes to a given target node.
• Second, LQANR outperforms real-valued or called continues representation methods. The results show that low-bit representation does not necessarily lead to embedding accuracy loss compared to continues embedding. By forcing discrete constraint to the learning function, we add the non-linear factors to the matrix factorization objective function. This operation may help to avoid over-fitting problem.
• Third, LQANR outperforms NetHash and BANE which can only generate binary representation. Our method can obtain any low-bit embedding not constraint to binary, which is more flexible and accurate to capture attributed network information.

5.3 Link Prediction Results

Table 3 shows the results of link prediction. The bit-width is {-1, +1}. We summarize the observations as follows:

• First, LQANR significantly outperforms baselines on the Cora and Citeseer datasets. The AUC score reaches as high as 93.85% on Cora and 96.51% on Citeseer.
• Second, LQANR outperforms baselines using realvalued representations. Converting real-valued numbers into low-bit discrete representation can improve the link prediction accuracy because the low-bit representation can alleviate the over-fitting problem and it is preferable to deliver Yes or No for recommendation.

5.4 Speedup of LQANR

In addition to the superior performance of LQANR with respect to AUC, low-bit representation also accelerates link prediction speed by replacing the dot-product similarity computation with bit-wise Hamming distance. The speedup of 100 and 200 dimension nearest search via hamming distance compared to dot-product is shown in Figure 2. The results show that large-sized networks gain significant speedup.

5.5 Parameter Study

In this part, we test four parameters, bit-width decided by N, embedding dimension d, proximity matrix maximum order K and weights of Pk impacted by r .

Bit-width decided by N. We study different kinds of bitwidth for discrete node embedding. We test binary quantization, ternary quantization, one-bit shift quantization and two-bits shift quantization. The node classification result on the Cora dataset with respect to different bit-width values is shown in Table 4. We can observe that the classification accuracy increases with bit-width. For example, the Micro-F1 score increases from 80.16 when B is represented by {-1,1} to 83.51 when B is represented by {-4,-2,...,2,4}. In our experiments, we set B as {-1,0,1} if not specially mentioned.

Node embedding dimension d. We test the embedding dimension d from 20 to 200 with a stepsize of 20. The link prediction results are shown in Figure 3(a). We can observe that the performance of network embedding improves with d increasing from 20 to 100, and then remains stable when code length continuously increases. On the BlogCat-

(b) Weights of αk on Citeseer alog dataset, the link prediction results are the lowest. This is because BlogCatolog contains more complicated structure and attribute information than the other datasets.

Table 5. Node classification (Micro-F1) w.r.t. K on Cora

Proximity matrix order K. We test node classification with different K. The results on Cora with K arranging from 2 to 6 are shown in Table 5. It shows that K = 5 is the best choice for Cora in many cases. The reason is that when K is too large, it can cause over-smoothing for node attributes. However, small K cannot fully propagate node attribute information in networks.

Weights of Pk impacted by r. Different k-hop Pk matrices capture different steps of neighboring node attributes. The layer-wise weights αk are impacted by r. We test on different datasets and find the best node classification results with the best parameter r. r is usually between 1 and 10 for the tested datasets. We plot the distribution of αk on Citeseer with K = 5 and r = 1.6. From Figure 3(b), we can observe that the higher order Pk contributes heavier weights, which means combining more layers leads to better results.

6 Conclusions

In this paper we study a new problem of Low-Bit Quantization for Attributed Network Representation Learning (LQANR). We use a k-hop proximity matrix to jointly encode data dependence between node links and attributes. Based on the k-hop proximity matrix, we formulate a new learning function that simultaneously learns the low-bit node representation and the layer-wise aggregation weights. Experimental results validate the performance of the proposed model. In the future, we will combine graph signal processing methods with low-bit neural network compression methods so as to learn more concise network representations.

Acknowledgements

This project was supported by ARC Discovery Grant DP180100966, NSFC (No. 61872360) of China and an Australian Government Research Training Program Scholarship.