Crafting Efficient Neural Graph of Large Entropy

1 Introduction

The success of Convolutional Neural Networks (CNNs) comes with massive parameters computation and storage. A wide variety of models with deeper architecture have been exploited in recent years and have achieved state-of-the-art performance in many computer vision applications, such as image classification and object detection. [Simonyan and Zisserman, 2014; He et al., 2016; Huang et al., 2016] However, due to the high computation costs and run-time memory, those deep networks cannot be directly deployed to some resource constrained platforms, such as mobile devices and embedded sensors, which has great application potential.

Thus, reducing the storage and computation usage of deep CNN models has received increasing attention [Hassibi and Stork, 1993]. Recently, some compression algorithms have been further explored to achieve satisfactory performance in deeper and large-scale CNN model compression [Zhou et al., 2016; Yang et al., 2016; Luo et al., 2017; You et al., 2017; He et al., 2017; Yu et al., 2017; Wu et al., 2018; Bansal et al., 2018]. By pruning the neurons or channels, the network can be more sparse and efficiency of networks can be improved. [Han et al., 2015] proposes to prune the neural connections with small weights. [Li et al., 2016] proposes to prune the channels with small weights and then fine-tune the network. [Yang et al., 2016] proposes a pruning algorithm by minimizing the error in the output features. [Luo et al., 2017] prunes the channels according to the feature reconstruction error. [Yu et al., 2017] propagates the feature ranking on the final response layer to obtain neuron importance scores. [Liu et al., 2017] proposed to make use of the scaling factors in Batch normalization [Ioffe and Szegedy, 2015] for pruning channels. [Zhang et al., 2018] formulates pruning as a constrained nonconvex optimization problem.

∗This work was done when Hanting Chen worked as an intern at Huawei Noah's Ark Lab

Typical network pruning techniques focus on keeping important weights and fine-tune pruned models. However, recent works argue that the pruned architecture itself contributes to the final efficiency [Liu et al., 2018]. Getting lost in manipulating individual neurons or channels, we could ignore the big picture of the neural network. To illustrate, we constructed two toy networks of 2 layers with same number of connections under different algorithms. The random algorithm is constructed by randomly selecting the neural connections in the neural graph, whereas the regular algorithm randomly selects the neural connections under the constraint of regularity. For example, poor regularity may block data flows and hinder neurons or channels from getting involved in the network, as shown in Figure 1a, which is generated by random algorithm. It is therefore necessary to have a thorough investigation on the characteristics displayed by the neural network as a whole (see Figure 1b), which forces all the vertices on the same side have similar degrees.

In this paper, we propose to craft efficient deep neural network through a graph lens. Structural complexity reveals the way in which vertices and edges are arranged in the graph, providing a significant influence on the graph function and performance. Graph entropy offers an attractive route to such complexity measures. To increase the capacity of the pruned network under a particular network sparsity, we maximize graph entropy of the network by optimizing the arrangements of neurons and connections. We identify important weights from the pre-trained over-parameterized network, and use them in preference to others in crafting our efficient neural network. Based on the resulting sparse network architecture, we train the network parameters from scratch rather than adapting their original weights. The proposed algorithm can be easily deployed to many popular network architectures, such as ResNet [He et al., 2016], VGG networks [Simonyan and Zisserman, 2014] and DenseNet [Huang et al., 2016]. Experimental results on ImageNet and CIFAR datasets [Krizhevsky, 2009; Deng et al., 2009] demonstrate that deep neural networks can be well compressed by investigating graph entropy while preserving the accuracy.

2 Methodology

Pruning neural networks is to compresses networks by deleting neurons or neuron connections from a trained model, which has been paid more attention to in recent years. However, most pruning techniques only involve local operations and do not take whole network proprieties into consideration, which may block information flows from layer to layer. In contrast, we take neural network architecture as a graph, and construct sparse graphs with a global viewpoint to initialize the network architecture before the training phase. To encourage better information flow in the network, we employ Von Neumann Entropy as a measurement to assess the qualities of graphs, which leads to a favorable tradeoff between accuracy and sparsity of the neural network.

2.1 Von Neumann Entropy

Von Neumann Entropy is an extension of the Gibbs entropy to the quantum field, which can be treated as a quantitative measure of mixedness of density matrices [Braunstein et al., 2004]. Recently, considering its capability of describing spectral complexity, centrality, and entanglement of the graph, Von Neumann Entropy has been further explored to evaluate graph entropy in various graph pattern recognition and analysis applications. The definition of Von Neumann Entropy is given as

where tr denotes the trace of matrix and ρ is the density matrix. ρ could be a Laplacian matrix LG scaled by degree sum of graph G, i.e. ρ = 1 dG LG. Given λi as the i-th eigenvalue of density matrix ρ, Von Neumann Entropy can be re-written in terms of spectrum of ρ as

The Shannon entropy computes the uncertainty of global spectral parameters of graph, involving all the eigenvalues, which makes it a useful and general measurement. Here we pay more attention to properties of Von Neumann Entropy.

To illustrate, we first constructed two toy graphs with the minimum and maximum entropy using greedy algorithm to explore its properties, as shown in Figure 2. We observed that given a fixed number of edges, if there are more connected clusters that are disjoint unions of highly fully-connected subgraph, the graph will have a smaller entropy. This is consistent with the results in [Passerini and Severini, 2008]. The entropy of the graph in Figure 2 (a) is 2.554. Almost half of connections from the first layer to bottom layer have been blocked and several vertices are deactivated due to the minimum entropy construction. On the contrary, a "balanced" graph that has a higher regularity tends to have a larger entropy. A more rigorous proof will be given later. For example, we plot a graph that is constructed with the maximum entropy given 50 edges in Figure 2 (b) whose entropy is 2.875. All vertices on the same layer have similar degree, which produces a balanced graph and results in better connections and data flows. If a graph is more balanced, every neuron would be more active in contributing to the entire neural network, which results in a better network performance.

An efficient deep neural network is expected to have a better inner connection for data flows and high-sparsity for efficient compression, a graph of large entropy exactly tickes all the boxes. Consider the neural graph G = (V,E), where V is the set of vertices with size n and E is the set of edges with size m. We can use greedy algorithm to maximize the entropy of graph. We simply compute graph entropy increment by adding all the possible edges and select the one which contributes the maximum increment. Algorithm 1 shows the details of it. After the neural graph construction, a network can be easily crafted from the graph.

For a linear layer, it can easily built by treating vertices as neurons and edges as neuron connections. For a convolu-

Algorithm 1 Neural graph generation with greedy algorithm

Input: number of total edges m, number of edges to select m′ Output: graph G with size of m′ Initialize graph G = [] Initialize edges E with size m, which are edges of complete neural graph (fully connected) repeat Entropymax = 0 for i = 0 To i = |E| - 1 do Entropy(G ∪ Ei) = EntropyofG ∪ Ei if Entropymax < Entropy(G ∪ Ei) then Emax = Ei Entropymax = Entropy(G ∪ Ei) else Continue end if end for Add edge Emax to G until |G| is m′

tional layer, it can be built by a similar way where we treat vertices as channels and edges as filters. The number of connections or size of filters depends on hyper parameter m′ , which is the number of selected edges in Algorithm 1.

However, greedy algorithm often takes lots of time to craft graphs. To select an edge added to graph, we need to compute the Entropy increment for all the possible edges with size m and computation of Von Neumann Entropy takes O(n3 ), so each step in greedy algorithm takes O(mn3 ) and the total complexity becomes O(m2n3 ). Thus, we tried making use of properties of graph entropy to reduce the complexity.

2.2 Regularity of the Graph

In graph theory, a graph is taken as regular, if its vertices have the same degree or valency. "Regularity" thus describes the extent of the graph to be regular, and can be computed as

where std denotes the standard deviation and d denotes the degrees of all vertices in the graph.

We found that regularity has a strong connection to Von Neumann Entropy. By approximating Von Neumann Entropy using quadratic entropy [Lin and Zhou, 2018], we have

where In is an identity matrix. Recall ρ = 1 dG LG and the degree sum of graph dG = 2m. Eq. 4 can be rewritten as

Based on the properties of Laplacian matrix that LG is symmetric and the trace of it is equal to 2m, entropy approximation can be rewritten in a form of degree, computed as

Algorithm 2 Random regular neural graph generation

Input, output and Initialization are same with Algorithm 1 Initialize D with the size of n to record the degrees

repeat

For edge [a, b] in E, compute the squared sum of degree dS = (da + 1)2 + (db + 1)2

Find the edges with minimum dSmin from E, marked as E′

Randomly select one edge [u, v] from E′

Add edge [u, v] to G

Update Du and Dv in D

until |G| is m′

where dv denotes the degree of vertex v. Given an edge (a, b) between vertices a and b, the increment in entropy of adding this edge to graph can be computed as

From Eq. 7, it is obvious that the increment of entropy depends on da and db. Graph G can obtain more increment in entropy if vertices a and b have smaller degrees. We reduce the cost of searching, by simply choosing the vertices pair with smallest squared sum of degrees in each step, instead of computing the entropy increment of adding all the possible edges, which reduces computation complexity to O(m2 ). Algorithm 2 shows the details of our regular construction. The complexity can be further reduced by exploring the vertex degree boundaries. The objective is to minimize the squared sum of degrees and we can derive a lower bound by making use of inequality as

From Eq. 8, we obtain a sub-optimal solution by directly minimizing the lower bound da + db, which can be used to further decrease the complexity based on Proposition 1.

Proposition 1. The degrees of all vertices are in range [⌊ 2m |V | ⌋, ⌈ 2m |V | ⌉].

Proof. To prove it by contradiction, we assume the opposite. (a) If there exists a vertex X has degree of ⌈ 2m n ⌉+1, all other vertices have minimum degree of ⌈ 2m n ⌉ or X cannot be selected. And the sum degree of graph will be 2m+ 1, which conflicts with the definition of graph. (b) If there exists a vertex X has degree of ⌊ 2m n ⌋ - 1, X has not been assigned to an edge added to the graph in the final step, which conflicts with the principle that we choose the vertices pair with smallest degrees. Thus all the degrees of vertices are in range [ 2m n -1, 2m n ].

Based on proposition 1, high regularity is the property our target graph must have and we simply adopt random algorithm to generate a graph with high regularity by randomly Algorithm 3 Regular neural graph generation with importance weights

Input, output and Initialization are same with Algorithm 1 Additional Input: importance scores S Sort S in descending order Sort E according to S repeat Select edge [u, v] from E in order if degree(u) < Umaxd and degree(v) < Vmaxd then Add edge [u, v] to G else Continue end if until |G| is m′

adding edges to graph while restricting degree upper boundary of all the vertices, which reduces computation complexity to O(m). In terms of models which contains massive layers and neural connections, we can simply divide the entire network into several subnetworks, which further reduces the complexity of construction.

2.3 ImportanceWeight

Although we reduce the construction complexity, the output graph is not fixed due to the random algorithm which randomly select the edge with minimum squared sum of degrees because there is no criterion for selection when the graph exists multiple vertices pairs with minimum sum, which makes the performance unstable, shown in Algorithm 2. Thus, we introduce importance weights which can be easily obtained to tackle this problem by giving the selection criterion.

Importance Estimation By Gradient

The role of importance estimation is illustrated in Figure 3. Given the network N and input x, the output of network is N(x; θ), where θ denotes weight parameters of network. The neuron connections (for FC layer) or filters (for CNN layer) may have different levels of importance according to the sensitivities of output to the infinitesimal changes on them. The output difference under perturbation can be estimated by simply computing the gradients of them as

where ϵ is the perturbation on weight parameters and k is the number of parameters in the network. From Eq. 9, the sensitivity depends on the gradients of learned network with respect to the weight parameters on input x. Thus, we can obtain estimated importance weights by computing their gradients as

where M is the number of examples from dataset. From Eq. 10, importance weights can be computed by M times backwards on a pre-trained model and selected dataset, which assists our initial sparse network to pay more attention to these connections with more important data flows.

Algorithm 3 shows the details of our proposed algorithm. With importance weights, we can construct the entire neural graph with high regularity by adding edges one by one according to their importance levels instead of random selection algorithm, shown in Figure 3. Thus importance weights guarantee that edges which tend to have important data flow will be added to the graph, which makes the generated network adaptive to the specific dataset so that our network has more stable performance and gains better trade-offs.

Our final algorithm, regular algorithm with importance weights (RAIW) has taken both graph entropy and importance weights into consideration, which improves the efficiency due to graph entropy and guarantees the stability due to importance weights. The entire process of crafting neural graphs is shown in Figure 3. The edges with high importance will be added to our neural graph if it does not destroy the regularity of graph. For example, the edge with the top importance weights 0.01 cannot be added to our neural graph because it connects those vertices with higher degrees, thus the edge with value of 0.005 is added instead, shown in the final step in Figure 3.

3 Experiments

To evaluate the efficiency of our algorithms, we apply our RAIW algorithm to generate neural graphs based on different popular CNN architectures, such as VGG, Resnet and Densenet. For comparison, we repeat the experiments on different datasets, such as CIFAR10, CIFAR100 and Imagenet, with these architectures under various layer settings and compare them with pruning techniques or the original models to demonstrate better trade-offs of our algorithm. The stability and regularity will also be discussed.

3.1 ComparisonWith Efficient CNNArchitectures And Pruning Algorithms

VGG on CIFAR10

We compare our algorithm against some popular pruning techniques, [Han et al., 2015; Li et al., 2016; Liu et al., 2017] [Liu et al., 2017] which achieve good performance among pruning techniques. To evaluate the performance of RAIW, we evaluate on CIFAR10 [Krizhevsky, 2009] with VGG-16 architecture. The detailed results are shown in Table 1. Our algorithm can preserve the accuracy, which has 0.6% drop but only 1.1M parameters, almost 14X compression rate.

Densenet and Resnet on CIFAR100

To evaluate the robustness of our algorithm, we deploy RAIW on Densenet and Resnet running on CIFAR100 dataset [Krizhevsky, 2009]. We sparse these models by crafting convolutional layers whose filter size is half of the original one by controlling the number of selected edges in algorithms.

For Resnet on CIFAR100, we run Resnet with different number of layers on CIFAR100 dataset. We compare our algorithm with these base models by comparing the 1-crop error along with the number of parameters of model, the details are given in Figure 4 (a). Our algorithm consistently has a better performance with the similar parameters, comparing the two lines in Figure 4 (a). For example, the original Resnet-56 has 0.86M parameters number with 28.89% error, however, our RAIW algorithm which has the similar parameter number on Resnet-110, has 0.8% error drop.

For Densenet on CIFAR100, we run with Densenet-BC which contains bottleneck layers and uses Densenet-BC-4024, 40-48, 40-60 which have 40 layers and different growth rates as base models. Again, we show better accuracyparameters trade-offs, the details are given in Figure 4 (b). Similarly, comparing the two lines in Figure 4 (b), the network we crafted using RAIW algorithm can be more efficient. For example, RAIW algorithm has 21.07% error on Densenet-BC-40-60 with 2.10M parameters while the original Densenet-BC-40-48 has 21.37% error with 2.76M parameters, which demonstrates the efficiency of our algorithm.

Densenet and Resnet on Imagenet

To further evaluate the efficiency and generality of our algorithm, we also test on Imagenet [Deng et al., 2009] using the Resnet and Densenet architectures crafted by our algorithm.

For Resnet on Imagenet, we craft Resnet-50 and 101 and compare them to the original ones with similar parameter numbers. When the parameters number comes to 21M, our RAIW algorithm on Resnet-101 can gain a slightly better accuracy than Resnet-34 with less parameters, shown in Table 2 with bold. For Densenet on Imagenet, we craft Densenet-169, Densenet-201 and compare them to the original ones. For each Densenet model, RAIW has approximately 3% accuracy drop but only 40% parameters of the original one. Thus, RAIW can obtain better accuracy-parameters trade-offs and improve the efficiency of popular CNN architectures.

3.2 Stability Of Model

To evaluate the stability of models under constructions of different algorithms, we repeat the experiments on CIFAR10 with VGG16 architecture. For each algorithm, we repeat 5 times and compare their mean accuracy and standard deviation. We compare the regular algorithm 2 with RAIW 3 to demonstrate the role of importance weights.

The results are shown in Table 3, the random regular algorithm tends to have large variation on the accuracy due to the random initial construction. Although they force graphs to be regular to different extents, there still exists high uncertainty because different connection distributions always have different performance, which results in relatively high standard deviation, shown in the first row with 0.17. In contrast, our RAIW algorithm has relatively high mean accuracy and low standard deviation with 92.85 ± 0.12 (shown in the last row) because once the importance weights are computed, the neural graph is fixed, which makes the performance more stable and the graph can be stored for multiple-times use, which saves the computation resources. Thus, RAIW algorithm improves the stability of regular algorithm, which makes it easily deployable.

3.3 Role Of Regularity

Due to regularity, d can be hyper parameters we use to sparsify the network, where d denotes the degrees of all the vertices. And accuracy relies heavily on it due to the trade-offs between sparsity and performance. In this section, we run VGG16 model on CIFAR10 under different regularity to evaluate trade-offs of our algorithms, as shown in Table 4.

We have tried 3 different sparsity, marked as d - 32, d - 16, d - 8, and details of each layer are given in the Table 4. Compared with original VGG16 architecture which gains 93.86% accuracy with 14.98M parameters, our crafted neural graph d - 32 obtains "14x" compression rate with only 0.6% accuracy drop. Furthermore, d - 16 with "20x" compression rate and d - 8 with "27x" compression rate, both have relatively small accuracy drop.

The reason why our constructed architecture allows high sparsity is that our algorithm increment on graph entropy is much faster than other ones, as shown in Figure 4 (c). For the simplicity, we construct two subnetworks and each of them contains neural connections of two layers, which are 256∗256 and 512 ∗ 512. The blue and green curves denote the entropy increment along with the increasing of edge number under our algorithm 2 while the orange and red ones denote random one. It is obvious that our algorithm keeps obtaining large entropy increment during the edge construction. The graph entropy almost reaches its peak when we select d = 8 where number of edges are 256 ∗ 8 = 2048 for 256*256 layer and 512∗8 = 4096 for 512*512 layer. We found it interesting that d = 8 is exactly the sparsity we have selected for d - 8 and that's the sparsity where we found the accuracy tends to have a relatively larger drop. Thus, we believe that the accuracy is highly related to entropy value. As a result, our algorithm guarantees maximum increment of entropy so that it can gain large entropy with less edges, which enables our model to have high sparsity.

4 Conclusion

Notice the strong connection between nerual networks and graphs, we tried to improve the efficiency by construct neural graphs which have better vertices and connections arrangement. Thus, we propose to craft efficient neural networks based on the properties of graph entropy. We reduce the computation complexity of graph generation to make it deployable and make use of importance weights to guarantee stability. Our RAIW algorithm achieves better trade-offs compared to pruning algorithms and efficient CNN architectures.

Acknowledgements

This work was supported in part by the Australian Research Council under Project DE180101438.