{'fraction_non_alphanumeric': 0.03079002703514569, 'fraction_numerical': 0.011414839291078402, 'mean_word_length': 4.587272727272727, 'pattern_counts': {'":': 0, '<': 5, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Differentiable Sparsification for Deep Neural Networks

Deep neural networks have relieved a great deal of burden on human experts in relation to feature engineering. However, comparable efforts are instead required to determine effective architectures. In addition, as the sizes of networks have grown overly large, a considerable amount of resources is also invested in reducing the sizes. The sparsification of an over-complete model addresses these problems as it removes redundant components and connections. In this study, we propose a fully differentiable sparsification method for deep neural networks which allows parameters to be zero during training via stochastic gradient descent. Thus, the proposed method can learn the sparsified structure and weights of a network in an end-to-end manner. The method is directly applicable to various modern deep neural networks and imposes minimum modification to existing models. To the best of our knowledge, this is the first fully [sub-]differentiable sparsification method that zeroes out parameters. It provides a foundation for future structure learning and model compression methods.


Introduction
The success of deep neural networks (DNNs) has changed the paradigm of machine learning and pattern recognition from feature engineering to architecture engineering [16,14,22,7,32]. Although DNNs have relieved the burden of feature engineering, comparable human efforts are instead required to design an effective architecture, such as by determining the number of neurons or layers and the connections between nodes. In addition, as DNNs grow ever larger (even up to 10-68 million parameters) [8,10,15,32], a considerable amount of effort is also being invested in reducing the sizes of existing models and in being able to deploy such networks on constrained platforms with acceptable latency periods [26,25].
These problems can be addressed by sparsification of an over-complete model [20]. A network structure can be carved out of an over-complete model by removing redundant blocks [3,29] or deleting unnecessary connections between nodes or blocks [2,18,30], which also reduces the network size. Among several approaches, pruning has long been adopted [17,6,26,19,5]. It typically applies several steps to a pre-trained model (select the unimportant parameters of a pre-trained model, delete those parameters, and retrain the pruned model) and may repeat each of these steps multiple times. Another popular approach is sparse regularization with a proximal gradient [21,3,29,33], which shrinks redundant parameters to zero during training and does not require a pre-trained model. Among the most popular tools is l 1 -regularizer [28]. However, as it acts on an individual parameter, it often produces unstructured irregular models; thus, its use diminishes the benefit of parallel hardware computation, such as that done through GPUs [29]. In order to obtain regular sparse structures, a sparse regularizer with l 2,1 -norm [3,29] was adopted on a group of parameters so that all parameters under the same group are either retained or zeroed-out together. By zeroing-out parameters at the group level, it is possible to determine the number of neurons or layers automatically as a part of the training process. However, the regularization terms are optimized in a separate process from the gradient descent-based optimization process for prediction loss. The update rules should be implemented manually and the approach is limited to cases in which closed-form solutions for the proximal operation are known.
In this work, we propose a fully [sub-]differentiable sparsification method for DNNs, which directly optimizes a regularized objective function and allows parameters to be exactly zero during training via stochastic gradient descent. Thus, the method can simultaneously learn the sparsified structure and weights of DNNs in an end-to-end manner. It does not require manual coding of a pruning step or an update rule like a soft-thresholding operator, and it allows for simpler implementation. It can adopt various norms as a regularizer regardless of whether or not the closed form solutions for the proximal operator are known. Another advantage of the proposed method is that it can easily be applied to a group of parameters or a building block; thus, it can produce a structured model and maximize the benefits of parallel hardware computation (e.g., GPUs) and it suits the trend towards modularized design in deep learning [22,27,7,32].
2 Related Work

Proximal Gradient
Our proposed method is related to sparsity regularization with a proximal gradient [21]. A regularized objective function is written as where L denotes a prediction loss, R is a regularization term, D is a set of training data, W is a set of model parameters, and λ controls the trade-off between prediction loss and model complexity. The most popular regularizer is l 1 -norm, where w i is an individual element of W . To optimize the regularization term, parameter updating is performed with a proximal operator, where ← denotes an assignment operator, η is a learning rate, and (·) + represents max(·, 0). As this approach acts on an individual parameter, it often produces unstructured irregular models. In order to obtain regular sparse structures, the sparse regularization with l 2,1 -norm can be adopted [3,29]. All parameters in the same group are either retained or zeroed-out together. Regularization with l 2,1 -norm can be written as where W = {w g } and w g represents a group of model parameters. The regularization term is optimized with a proximal operator, When a group has only one single parameter, it degenerates to l 1 -norm regularization.
Another related group regularization method is exclusive lasso with l 1,2 -norm [34,33]. Rather than either retaining or removing an entire group altogether, it promotes competition or sparsity within the group. The regularization term is written as and its updating rule is derived as w g,i ← sign w g,i w g,i − ηλ w g 1 + .
These proximal operators consist of weight decaying and thresholding steps, and they are performed at every mini-batch or epoch in a separate step after the prediction loss is optimized. Therefore, some extra effort is required to implement the update rules manually. Moreover, the applications of this approach are limited to cases in which closed-form solutions for the proximal operator are known. In contrast, our approach directly optimizes a regularized objective function and allows parameters to be zero during training via stochastic gradient descent. It leads to simpler implementation and can employ various norms regardless of whether or not closed-form solutions for proximal operators are known, for example, p-norm with p < 1.

Differentiable Approach
Similar to our work, previous differentiable approaches [2,18] learn the structure of a neural network by optimizing architecture parameters in a relaxed continuous domain, where architecture parameters represent the importance scores of building blocks or the connection strengths between those blocks. However, as the architecture parameters cannot be zero during training, the top k connections or components are stochastically or deterministically selected according to the values of the architecture parameters to derive a discretized architecture. Therefore, the approach may suffer from the discrepancy between a learned architecture and a final discretized one. Moreover, the value of k must be pre-specified manually; thus, the same value is set for all blocks or modules, which may be sub-optimal. In contrast, our approach drives the architecture parameters to zero by directly optimizing a regularized objective function. Doing so can minimize the model discrepancy, and a network can choose different numbers of components or connections for each module during the training process.
3 Proposed Approach

Base Model
We assume that there are n components in a module. A component can be any building block for a DNN or its output. For example, it can be a channel or a layer of a convolutional neural network (CNN) such as ResNet [7,8] or DenseNet layer [10]. It can also represent a node in a neural graph [30] or a graph CNN [11]. A module represents a composite of components, such as a group of channels or a layer. For illustration purposes, we assume that a module y can be written as the linear combination of components f i or the concatenation: where x denotes a module input, w i represents the model parameters for component f i , and a i is an architecture parameter. The model parameters w i denote ordinary parameters, such as a filter in a convolutional layer or weight in a fully connected layer. The value of a i represents the importance of component i or the strength of the connection between nodes in another context. Forcefully setting a i to zero amounts to removing component f i or zeroing-out w i . Thus, creating competition between the elements of a and making them to be zero eliminates unnecessary components or connections. We will show that this simple sample model can be applied to various cases.

Differentiable Sparse Parameterization
First, we demonstrate how to parameterize architecture parameters with non-negative constraints, which is useful for an attention mechanism with the softmax function. To set up competition between the elements of a and allow them to be zero, we parameterize the architecture parameters as follows: where α i and β are unconstrained free parameters, σ(·) denotes a sigmoid function, and (·) + represents relu(·) = max(·, 0). When a parameter is non-negative, the proximal operator of Eq. (7) is reduced to Eq. (10). Although the forms are similar, they have completely different meanings. The proximal operator is a learning rule, whereas Eq. (10) is the parameterized form of the architecture parameters, and is part of the neural network.
We can easily verify that a i is allowed to be zero and is differentiable from a modern deep learning perspective. The free parameters α i and β are real-valued and do not restrict a training process that uses a stochastic gradient descent algorithm. Thus, we can train a i through α i and β. The exponential function in Eq. (9) ensures that the architecture parameters are non-negative. Typically, a i cannot be zero due to the exponential function in Eq. (9). However,γ i in Eq. (10) can be zero by the thresholding operation; hence, a i can be zero as well. The term σ (β) · γ 1 plays the role of a threshold. The thresholding operation is interpreted as follows: if the strength of component i in a competition group is low compared to the overall strength, it is dropped from the competition. Note that the scalar parameter β in Eq. (10), which determines the magnitude of the threshold, is not a hyper-parameter, but its value is automatically determined through training. Mathematically, the thresholding operator is not differentiable, but this should not be an issue considering the support of relu as a built-in differentiable function in modern deep learning tools. Additionally, γ is nonnegative; thus, its l 1 -norm is simply the sum of γ i (i.e., γ 1 = γ i ). The softmax of Eq. (11) is also differentiable. The softmax is optional but useful when it is necessary to promote competition between components, as in the attention mechanism.
Similarly, a singed architecture parameter can be formed as where α and β are free parameters. The gradient of the sign function is zero almost everywhere, but this is not a problem for modern deep learning tools. The equation can be rewritten as where (·) − = min(·, 0). The gradient can be computed separately according to whether or not its value is negative. To the best of our understanding, TensorFlow [1] already deals with the sign function in the explained manner, so tf.math.sign() can be used without manually implementing the conditional statement.

Sparsity Regularizer
In the proposed approach, a regularized objective function is written as where a denotes the vector of architecture parameters. Sparsifying a is equivalent to sparsifying a DNN. Therefore, the regularization term can be used on a to encourage the sparsity of the DNN. The proposed method is not limited to a particular norm. Also, different sparsity patterns can be derived depending on the type of norms. For example, the most popular choice for parameter selection is l 1 -norm, but it is unsuitable for a in Eq. (11) as it is normalized using the softmax function. The l 1 -norm of that parameter is always 1, i.e., a 1 = n i=1 |a i | = 1. Therefore, we should employ p-norm with p < 1: where the second equality holds as a i is always non-negative. To the best of our knowledge, a closed-form solution for the proximal operator of p-norm with p < 1 is not known and the proximal gradient method will not work. However, the regularization term is differentiable almost everywhere as is relu. Thus, the proposed approach can directly optimize the regularized objective function and zero-out components with stochastic gradient descent.
By simply switching one norm to another for the regularizer, it is possible to derive different sparsity patterns for a DNN. For example, an individual component can be removed with l 1 -norm (Eq. 2) and a group of components or an entire module can be zeroed-out with l 2,1 -norm (Eq. 4). Note that it is not necessary to manually implement different updating rules as in the proximal gradient approach. Instead, we can simply rewrite a regularization term in the objective function. Examples codes and experimental results are shown in the supplementary material.

Rectified Gradient Flow
If γ i Eq. (10) or α i in Eq. (12) is less than the threshold, the gradient will be zero, and the component will not receive learning signals. However, this does not necessarily mean that a component permanently dies once its importance score falls below the threshold. The component may recover because the threshold is adjustable and the importance scores of other components may decrease. Nevertheless, to ensure that the architecture parameters of dropped components continuously receive learning signals, we propose approximating the gradient of the thresholding function. As in [31], where the gradient of a step function was approximated using that of leaky relu or soft plus, we suggest employing elu [4] as a variant of the proposed method: relu is used in a forward pass, but elu is used in a backward pass.
This heuristic approach leads to a similar learning mechanism as that proposed in [30], where the gradient flows to dropped (or zeroed out) edges but does not flow through these dropped edges.
The architecture parameters in our proposed method correspond to the edges in [30]. Not that our approach is easy to implement and does not require additional codes to select dropped edges and control the gradient flow. We simply optimize the objective function using approximated gradients.
The implementation codes are shown in the appendix.

Application and Experiment
In this section, we show that the proposed approach can be used to reduce the size of a network as well as to learn the structure. Our aim is not to achieve state-of-the-art performance but to validate the basic idea and broad applicability of the proposed approach. In order to demonstrate its broad applicability using limited computing resources, we perform experiments with relatively small datasets, such as CIFAR-10/100 [13]. Our implementations closely follow those of baseline models, including in terms of the model structures and hyper-parameter settings. Network-slimming(NS) [20] prunes unimportant channels in convolutional layers by leveraging the scaling factors in batch normalization. Let x i and y i be the input and output, respectively, of batch normalization for channel i. Then, the operation can be written as

Channel Pruning in a Convolutional Network
where µ i and σ i denotes the mean and standard deviation of input activations, respectively, a i and b i are scale and shift parameters, and is a small constant for numerical stability. The scaling parameter a can be regarded as an importance score or an architecture parameter, and the affine transformation can be re-written as By forcing a i to be zero, the corresponding channel can be removed. Network-slimming trains an initial network with l 1 -regularization on a to identify insignificant channels. After the training, channels with small values of a are pruned. To compensate for the damage caused by pruning, a pruned network is re-trained. In our approach, we parameterize the scaling parameter using Eq. (12) and train a network with l 1 -norm on a using the stochastic gradient descent method without pruning and fine-tuning.
We perform comparative experiments on CIFAR-10/100 [13]. The training and test sets contain 50, 000 and 10, 000 samples respectively, and the final test error is reported at the end of training or fine-tuning on all training images. We adopt a standard data augmentation scheme (random shifting and flipping) as in [7,8]. In the network-slimming method, λ in Eq.(13) is fixed at 10 −5 , but in our approach, we vary its value to induce different levels of sparsity. DenseNet-BC-K12 (100 layers) [10] and ResNet (164 layers) [7,8] are employed as base networks. In the network-slimming method, pre-trained models are obtained by training networks for 160 epochs with an initial learning rate of 0.1. The learning rate is divided by 10 at 50% and 75% of the total number of training epochs. After the training process is complete, channels with small values of a are removed and a slimmed network is re-trained for additional 160 epochs with the same settings as in the initial training, but the learned weights are not re-initialized. In our approach, we train networks for 320 epochs without fine-tuning or re-training. Network-slimming initializes the scaling factor at 0.5 and we set α i = 0.5 (n + 1) /n and β = log n 2 + n − 1 in Eq. (12) so that a i starts at 0.5. Table 1 shows the experimental results on CIFAR-10 with DenseNet. The results of more experiments, including those using ResNet and CIFAR-100, are shown in the supplementary materials. The authors strongly urge readers to peruse the supplementary materials. We ran each experiment 5 times; the data in the table are the average and standard deviation from these 5 repetitions. Our proposed method is called by Differentiable Sparsification (DS). We controlled the value of λ such that it has a similar sparsity rate as the network-slimming approach. In the tables, sparsity denotes the pruning rate, i.e, the number of removed channels in hidden layers. The experiments show that the proposed differentiable approach more effectively learns slimmed models than the other approach. Discovering Neural Wiring(DNW) [30] relaxes the notion of layers and treats channels as nodes in a neural graph. By allowing channels to learn inter-channel connections, it simultaneously discovers the structure and learns the parameters of a neural network. An input to node v, y v , is expressed as

Discovering Neural Wiring
where x u denotes the state of a preceding node, E represents an edge set and w u,v is the connection weight of an edge. The structure of a neural graph can be determined by choosing a subset of edges. At each iteration of the training process, DNW chooses the top k edges with the highest magnitude, which is called the real edge set, and refers to the remaining edges as the hallucinated edge set. On the forward pass or at inference time, only real edges are used. As DNW allows the magnitude of the weights in both sets to change throughout the training process, a hallucinated edge may replace a real edge when it becomes strong enough. The weights of real edges are updated in an ordinary manner  Figure 1: Left: Structure of a GCN block. Each block consists of a shared adjacency, an input feature, and a weight matrix. Each row and column of an adjacent matrix are treated as groups to enable learning of the relationships between a node (indexed by i) and its neighbors. Right: Row grouping creates competition between in-coming nodes, and column grouping creates competition between out-going nodes.
with stochastic gradient descent, but those of hallucinated edges are updated by a specialized leaning rule: the gradient flows to hallucinated edges but does not flow through them.
The architecture parameters in our proposed method correspond to the edges in DNW. We parameterize the edges using Eq. (12) and train a network with l 1 -norm on edges to induce sparsity. The rectified gradient leads to an update rule which is similar to that of DNW: the rectified gradient ensures that dropped architecture parameters continuously receive learning signals by approximating the gradient of the thresholding function. However, it is not necessary to keep track of the real and hallucinated edge sets. We simply optimize the objective function with approximated gradients. The rectified gradient can be implemented in a couple of lines using modern deep learning tools; the relevant code is shown in the supplementary material.
We perform experiments on CIFAR-10/100 [13]. The final test error is reported at the end of the training process. MobileNetV1 (×0.25) [9] is employed as a base model and our implementation closely follows that of DNW. We train the model for 160 epochs with an initial learning rate of 0.1. The learning rate is scheduled using cosine annealing. For DNW, we chose the value of k such that the final learned model has similar Mult-Adds as the base model. For the proposed method, we also set the value of λ in the same manner. Table 2 shows the experimental results on CIFAR-10. We ran each experiments 5 times; the results represent the average and standard deviation. Our approach is denoted DS. DS without the rectified gradient method corresponds to DNW-No Update, where hallucinated edges are not updated. Even without the rectified gradient, the performance of the proposed method is close to that of DNW with the update rule. This finding validates the effectiveness of our sparse parameterization. We also performed experiments with the proximal gradients in Eq.(3) and Eq. (7), which is denoted PG in Table 2. PG-l 1 -norm also uses the l 1 -norm as a regularizer, but the approach did not learn as effectively as ours. Similarly, PG-l 1,2 -norm uses the update rule of Eq.(7), the shape of which is similar to the proposed sparse parameterization in Eq. (12), but the performance of that method is worse than ours. The results of more experiments, including CIFAR-100, are shown in the supplementary materials due to page limitations. DNW determines the size and structure of a network by choosing k edges. However, it is not clear how the approach should choose k for different stages (or blocks), so it uses the same pruning rate for all stages. This may be a limitation because each stage plays a different role and may need a different amount of resources. In contrast, our approach controls the model complexity by adjusting the value of λ in the objective function, and a different amount of resources is allocated for each stage through training. As shown in Table 2, the proposed method uses model parameters more efficiently.

Learning relationship between nodes in a graph convolutional network
In this section, we apply the proposed approach to learn the structure of an adjacency matrix in a graph convolutional network (GCN). The purpose of this case study is to test whether our approach can learn semantic structure from data rather than reducing the size of a neural network or improving the prediction accuracy. We adopt the model in [11], which is one of the most successful GCN models. A GCN block or layer is defined (see Fig. 1) as where A is an adjacency matrix; H l and W l are an input feature and a weight matrix for layer l, respectively; and F is a nonlinear activation function. In general, A is non-negative and shared across GCN blocks. It is obtained by normalization. For example, whereÃ is an unnormalized adjacency matrix; andD is a diagonal matrix, whereD i = jÃ i,j . The adjacency matrix represents the connections or relationships between nodes on a graph and is usually given by prior knowledge. Learning the value of A i,j amounts to determining the relationship between nodes i and j. If the value of A i,j is zero, the two nodes are thought to be unrelated.
As shown in Fig. 1, we define each row and column as a group. Row grouping creates competition between in-coming nodes, whereas column grouping creates competition between out-going nodes. Each row and column of unnormalized adjacency matrixÃ can be parameterized similarly as inγ of in Eq. (10): The softmax normalization of Eq. (11) is replaced with Sinkhorn normalization [23,24,12] to make A doubly-stochastic (each row and column sum up to 1). After initializing A withÃ, we can convert A into a doubly stochastic matrix by iteratively applying the following equations: Note that although the normalization is iterative, it is differentiable. Balanced normalization is also possible by iteratively applying Through numerical experiments, we verified that iteratively applying the above equation also makes A doubly stochastic, but we could not find a theoretical justification for this observation. We leave the mathematical proof as an open question for a future work. As competition groups are created in row-and column-wise approaches, a regularized objective function can be written as where W = {W l }, N is the size of square matrix A, and A i,: and A :,i denote ith row and column vector of A, respectively. We employ l p -norm (Eq. (14)) with p = 0.5 as a regularizer.
To validate our purposed method, we applied a GCN to estimate future traffic speeds in a road network. The traffic speed data were collected from 170 road segments.Thus, the size of an adjacent matrix is 170 × 170. A map of the area from which data were collected is shown in Fig. 2. Onestep ahead observation is estimated from eight past observations and an output layer generates 170 estimates, one for each road segment. Prediction loss is measured using the mean relative error (MRE). More detailed specifications of the experimental data and our GCN model can be found in the supplementary material.
Three baseline models were used, where two were provided information on the connections between roads and the other was not. For the first baseline, we set the value of A i,j as a constant such that A i,j = 1 ni if node (or road) i and j were adjacent to each other (n i is the number of neighbors of node i), and A i,j = 0 otherwise. The second baseline used a similar approach, but we set A i,j = exp α i,j if node i and j were adjacent to each other to ensure that the strengths of the connections were learned. For the third baseline, no connectivity information was given. However, we setÃ i,j = exp α i,j for all i, j regardless of the actual connections. For the proposed method, we parameterized the adjacency matrix as in the third baseline but applied the sparsification technique with l p -norm for a regularizer. Balanced normalization was applied to all cases except the first baseline, for which the row sum is 1.
To measure the learned relationship between nodes, we propose the following scoring function: c , denotes the element-wise product, and [M k ] i,j = 1 if the geodesic distance between node i and j is less than or equal to k, whereas [M k ] i,j = 0 otherwise. The maximum value is 1, and the minimum is 0. For example, the first and second baselines always take the maximum value because their adjacency matrices have exactly the same structure as M 1 . We calculated the scores for k = 1 and 2. Note that we used A r and A c instead of A because a sparsified matrix is not guaranteed to be doubly stochastic even if the original Sinkhorn normalization method is adopted. The performance of the baseline models is shown in Table 3a. We ran each experiment five times and selected the median among the five lowest validation errors. For the first and second baselines, the road connectivity information is provided, and the number of non-zero elements of the adjacent matrices is 878. Note that the value of the learned relationship for Baselines I and II is constant, but it is shown for reference. The road connectivity information is not given for the third baseline, and the number of non-zero elements of the adjacent matrix is 28, 900(= 170 × 170). The performance of the proposed model is shown in Table 3b. The experiment using Baseline III shows that the GCN found a nonlinear mapping between input and target values simply by reducing the prediction loss without learning the semantic relationships between nodes, but the proposed approach learns the relationships between nodes. We further compared the proposed method with the proximal gradient method. The experimental results are shown in the supplementary material.

Scope and Limitations
Our aim is not to achieve state-of-the-art performance but to validate the basic idea and broad applicability of the proposed approach. To the best of our knowledge, this is the first fully [sub-]differentiable sparsification method that zeroes out components, and we hope that our work will provide a foundation for future structure learning and model compression methods. The main limitation of our approach is that a sparsity rate cannot be explicitly specified before training, as is done in conventional pruning approaches. If a specific sparsity rate is required, it should be obtained by trial-and-error. The rectified gradient can be effective as shown in the neural wiring experiments, but it is not clear what cases it applies to. More theoretical analysis is necessary, which we leave for a future work.

Conclusion
In this study, we proposed a fully differentiable sparsification method that can simultaneously learn the sparsified structure and weights of deep neural networks. Our proposed method is versatile in that it can seamlessly be integrated into different types of neural networks and used to address various problems.
[33] Jaehong Yoon and Sung Ju Hwang. Combined group and exclusive sparsity for deep neural networks. In ICML, 2017.

Sparsity Regularizer
In our approach, different sparsity patterns can be derived by adopting different norms for a regularizer. For example, an individual component (e.g., a channel) can be removed by l 1 -norm and a group of components or an entire module (e.g., a layer) can be zeroed-out by l 2,1 -norm. Note that it is not necessary to manually implement different updating rules as in the proximal gradient approach. Instead, we simply change a regularization term in an objective function. An implementation example with TensorFlow is shown in Listing 1.  Figures 1 and 2 show the sparsified structures of DenseNet-K12 with 40 layers, trained with l 1 -norm and l 2,1 -norm, respectively. Each row corresponds to one hidden layer. For sparse regularization with l 2,1 -norm, we create a group of 12 channels such that layer-wise connections can be learned. Fig. 1 shows the sparsified structures of the hidden layers in channel-wise. The pixel-like thin short strip represents the magnitude of a scale parameter in the batch normalization. Fig. 2 shows the Preprint. Under review. sparsified structures in group-wise. Each square block represents a group of 12 channels. One block is added at a time as a layer proceeds from top to bottom since each layer outputs 12 new channels. An input layer generates 24 channels; thus, the first row has 2 blocks. The number of surviving channels is represented by the color of the block, the brightness of which is proportionate to the number of non-zero channels within a group. Table 1 shows the sparsity rates for a base model, Network-slimming(NS) [7] and the proposed method (DS). Although the two cases of the proposed approach have similar channel-sparsity rates, the learned structures are very different. The experimental results show that the proposed sparse parameterization method is not limited to a particular norm and that it can learn different structures by simply changing norms.

Analysis of Gradient Flow
Assume that an output y of a neuron in a hidden layer is written as where x denotes an input from a preceding layer, w i represents the model parameters for component f i , and a i is an edge or an architecture parameter. A loss function can be denoted L a (α) , f (x; w) . Let a i be a function of α, a i (α i ) = sign (α i ) |α i | − σ (β) + , which is simplified for this analysis. The gradients can be written as (1) becomes zero and α i does not have a learning signal. If elu [1] is employed in the backward pass, the model can generate an approximate gradient for α i . Regardless of whether elu is used in the backward pass or not, w i and x do not receive a learning signal through a i since a i = 0 in Eq. (2) and (3). This leads to a similar learning mechanism proposed in DNW [8], where the gradient flows to zeroed-out (hallucinated) edges but not through them.
If we define a as in the main paper, the gradient is written as Even if elu [1] is not used in the backward pass, the gradient for α i is still generated through others. However, a more effective learning signal can be generated with elu.

Channel Pruning in a Convolutional Network
We compare the network-slimming (NS) method [7] and our proposed method (DS). We ran each experiment 5 times and show the average and standard deviation. We ensured that DS had similar pruning rate as the NS approach. Tables 2 and 3 show the experimental results on DenseNet with 100 layers [5], and Tables 4 and 5 on ResNet with 164 layers [2,3]. In the tables, sparsity denotes the pruning rate, i.e, the number of channels that are removed from hidden layers. When the sparsity rate is relatively low, the two approaches have similar error rates, but the difference between them increases as the sparsity rate goes up.

Data
A summary of the data reported in the main paper is shown in Table 8. There were approximately 70, 000 probe taxis operating in the metropolitan area where the data were collected. As the taxis operated in three shifts, more than 20, 000 probes on average ran at any given point in time. The traffic speed data covers 4, 663 links in the area, which includes major arterials. Speed data from probes in the metropolitan area were aggregated every 5 minutes for each road segment; if no probe passed a link during a 5-minute period, the speed was estimated based on speeds in the previous time periods or from the same time periods in the past. After preprocessing, the raw data were once again aggregated in 15-minute periods to maximize forecasting utility. A 15-minute period is the standard on which the highway capacity manual is based. As no information was available regarding probe counts, which contribute to averaging speed data, three speeds for a 5-minute period were averaged without weighting. Among the 4, 663 links for which speed data were available, we selected 170 links in the subarea (see Fig. 3). We expected that the speed data collected in this region would be free from missing observations as it is the busiest region in the metropolitan area, and most taxi drivers congregate in this region to find passengers. Following the generic conventions of machine learning, we used data from the previous eight months to train the proposed model and reserved the data for the latter two months to test the trained model.     Figure 4 illustrates our GCN implementation. The outputs of hidden GCN blocks are concatenated and fed to an output block. This was motivated by the dense connections of DenseNet [5]. The structures of the hidden GCN blocks are illustrated in the main paper. We trained the model for 500 epochs using Adam [6] with the defaulting parameter setting of TensorFlow. The initial learning rate was set to 0.0005 and multiplied by 0.5 at epochs 400 and 450.

Prediction Model with GCN
A training loss is defined by the mean relative error (MRE) where N is the number of road segments andỹ i and y i denote an estimate and actual future observation of travel speed on road segment i, respectively. We ran each experiment five times and selected the median among the five lowest validation errors. We reported the test error from the epoch with the median validation MRE. The report error was re-written in tables with mean absolute percentage error (MAPE) for accessability purposes; MAPE is defined by multiplying MRE by 100.   The l p -norm with p < 1 can induce strong competition within a group, but its closed-form solution for the proximal operator is unknown. Among the norms which have closed-form solutions, exclusive sparsity regularization can be a promising substitute for l p -norm with p < 1 because of its capacity to promote sparsity or competition within a group. We performed comparative experiments with the l 1,2 -exclusive norm [10,9]. As in the main paper, we created groups for the row and column vectors of an adjacency matrix. Note that the proximal operator should be applied to free variables and cannot be applied on γ or a of an adjacency matrix. Thus, we did not apply the exponential function on α and instead constrained the elements of an adjacency matrix to be non-negative by setting the initial values as 1.0 and modifying the proximal operator as α g,i ← α g,i − ηλ α g 1 + , where α g represents the row or column vector of an adjacency matrix before doubly-stochastic normalization. We applied the proximal operator at every mini-batch after updating the model variables with the gradient of the prediction loss.

Exclusive Sparsity Regularization
As above, we modified our proposed approach for the comparative experiments. We did not employ the exponential function but applied the differentiable thresholding operation described in the main paper,γ g,i = α g,i − σ β g · α g 1 + , whereγ g represents the row or column vector of an adjacency matrix before doubly-stochastic normalization. This approach simultaneously optimized the prediction loss and the exclusive sparsity regularizer, Regularization was applied on α rather thanγ in order to maintain consistency with the experiment on the proximal operator, where regularization was applied on free variables. Tables 9a and 9b show the experimental results using the proximal gradient and the proposed method, respectively. The proximal method learned the mapping between inputs and targets by reducing the prediction loss, but did not learn the relationship between nodes as well as our method. Our method seeks to strike a balance between the two by directly optimizing the regularized objective, and learns the relationships between nodes more effectively.
Note that it is more appropriate to apply regularization on γ rather than α, as this allows the threshold operator to receive the learning signal directly from the regularization term and better learn how to control the trade-offs. To be certain, we also performed experiments with regularization onγ before doubly-stochastic normalization: The experimental results with exclusive sparsity regularization onγ are shown in Table 10. Clearly, direct regularization onγ allows the model to better learn the relationships between nodes.
Note that we could not apply l 1,2 -norm regularization on the row or column vectors of an adjacency matrix after performing doubly-stochastic normalization as the values of l 1,2 -norm are scaled to 1 by the normalization process. Again, the best approach is to apply regularization on the row or column vectors of an adjacency matrix after doubly-stochastic normalization as in the main paper, but this is not possible for the proximal gradient method, as discussed above. This shows the flexibility of the proposed approach.