Learning Connectivity of Neural Networks from a Topological Perspective

We represent the neural network using a directed acyclic graph (DAG) in topology. Specifically, we map both combining (e.g., addition) and transformation (e.g., convolution, normalization and activation) to a node. And connections between layers are represented as edges, which determine the flow of information. Then we can get a new representation of the architecture $\mathcal{G}=(\mathcal{N},\mathcal{E})$, where $\mathcal{N}$ is the set of nodes, and $\mathcal{E}$ denotes the set of edges.

In the graph, each node $n_{i}\in\mathcal{N}$ performs a transformation operation $o_{i}$, parametrized by $\mathbf{w}_{i}$, where $i$ stands for the topological ordering of the node. While the edge $e_{ji}=(j,i,\alpha_{ji})\in\mathcal{E}$ means the flow of features from node $j$ to node $i$, and the importance of the connection is determined by the weight of $\alpha_{ji}$. During forward computation, each node aggregates inputs from preorder nodes where connections exist. Then it performs a feature transformation to get an output tensor $\mathbf{x}_{i}$. And $\mathbf{x}_{i}$ is sent out to the postorder nodes through the output edges. It can be seen in the left of Fig. 2. It can be formulated as follows:

In each graph, the first node in topological ordering is the input one, which only performs the distribution of features. The last node is the output one, which only generates final output of the graph by gathering preorder inputs. We also propose an adjacency matrix as the memory space to store weights of edges. As shown in the right of Fig. 2, each row denotes the weights of input edges, and each column is the outputs. For nodes where there are no edges attached, the corresponding $\alpha$ is $0$. The dimension of row(with $\alpha\neq 0$) is called in-degree for a node, and the dimension of column(with $\alpha\neq 0$) is named as out-degree.

For a network with $k$ stages, $k$ DAGs are initialized and connected in series. Each graph is linked to its preceding or succeeding stage by output or input node. We rewrite the weights of nodes as $\mathbf{w}_{i}^{k}$ and the weights of edges as $\alpha_{ji}^{k}$. For the $k$-th stage, $\mathcal{T}^{k}(\cdot)$ denotes the mapping function established by $\mathcal{G}^{k}$ with parameters of $\mathbf{W}^{k}$ and $\boldsymbol{\alpha}^{k}$, where $\mathbf{W}^{k}$ is the set of $\{\mathbf{w}_{i}^{k}\}$, $\boldsymbol{\alpha}^{k}$ is the set of $\{\alpha_{ji}^{k}\}$. Given an input $\mathbf{x}$ and corresponding label $\mathbf{y}$, the mapping function from the sample to the feature representation can be written as:

By defining the topological perspective of neural networks, most previous networks can be reformulated from the natural perspective. For definiteness and without loss of generality, we selected the widely used residual connections for analysis [10, 31, 45]. A block with residual connection formulates $x+\varphi(x)$ as a basic component, in which $x$ represents the identity shortcut, and $\varphi(x)$ denotes the residual mapping. Normally, the residual component is composed of several repeated weighted layers. We call the number of repeats as interval, which is noted as $l$. Fig. 1 presents two residual architectures with a interval of $1$ and $2$ respectively. By using Eql.(1), we map the architecture from the natural perspective to the topological perspective. We give an example of this mapping in red lines. From a natural perspective, the layer acquires information through skip connections. In the new topological perspective, the node obtains information by corresponding edges. It should be pointed out that these two perspectives are completely equivalent in results. It also can be seen that the residual connections are rather denser than the original view, and perform multiple feed-forward paths instead of a single deep network. Our topological view explains the reason why residual connectivity is effective from a new aspect different from [40].

If the interval degrades to $1$, as shown in the right of Fig. 2, its topology evolves into a complete graph. Structurally, all nodes are directly connected to the input and output, resulting in indirect access to the gradients and the original input. Different from stacking blocks using predefined connectivity, the complete graph provides all possible connections and is suitable to be the search space. For a complete graph with $N$ nodes, the search space contains $2^{N(N-1)/2}$ possible topological structures. For a network with $k$ stages, the total search space can be noted as $\prod\nolimits_{k}2^{N^{k}(N^{k}-1)/2}$. And it is much wider than cell-based or block-based approaches [37, 8, 12]. By assigning learnable parameters which reflect the magnitude of connections to edges, it changes to a weighted graph. Within the search space, the connectivity can be optimized by learning continuous weights of edges.

We put forward a differentiable type to optimize the topological connectivity by learning a set of continuous weights of edges $\boldsymbol{\alpha}$. And they are learned simultaneously with all the other weights in the network via the loss generated by the concurrent task, noted as $\mathcal{L}_{t}(\cdot)$. Different from [1], we do not transform the weights of $\boldsymbol{\alpha}$ into binary. This allows us to assign discriminating weights to different feature inputs. Different from the selection of node type [21], we do not select the maximum input edge using $\arg\max$ operation. Instead, the continuous weights guarantees the consistency between training and testing. The optimization objective can be viewed as:

Set $\frac{\partial\mathcal{L}_{t}}{\partial\mathbf{w}_{i}}$ be the gradients that the network flows backwards to $\mathbf{w}_{i}$. And let $\frac{\partial\mathcal{L}_{t}}{\partial\mathbf{x}_{i}}$ be the gradients to $\mathbf{x}_{i}$. Then the gradients update to $\mathbf{w}_{i}$ and $\alpha_{ji}$ are of the form:

where $\eta$ is the learning rate, and $\odot$ indicates entrywise product.

Since the features generated by different layers exhibit different semantic representations, they contribute differently to subsequent layers, resulting in diversities of the importance of connections. Much as the mammalian brain [28] in biology, where synapses are created in the first few months of a child’s development, followed by gradual re-weighting through postnatal knowledge, growing into a typical adult with relative sparse connections.

To facilitate this process appropriately, we raise to attach sparsity constraint as a regularization on the distribution of weights of edges. Similar thought also has been verified in hashing representation [42] that sparsity can bring effective gain through minimizing a hash collision. We choose L1 regularization, denoted as $\mathcal{L}_{1}(\cdot)$, to penalize non-zero parameters of edges resulting in more parameters near zero. This sparsity constraint promotes attention to more critical connections. Then the loss function of our proposed method can be reformulated as:

and $\lambda$ is a hyper-parameter to balance the sparse level. Due to the properties of a complete graph, we propose two types to update $\boldsymbol{\alpha}_{ji}$. The first one is uniform sparsity that attaches constraint on all weights of edges uniformly. And let $\frac{\partial\mathcal{L}_{1}}{\partial\mathbf{x}_{i}}$ be the gradients to $\mathbf{x}_{i}$, we rewrite the Eql.(5) as:

The second one is adaptive sparsity which is logarithmically related to the in-degree $\delta_{i}$ of a node $n_{i}$. It performs larger constraints on dense input and smaller on sparse input. For the nodes with fewer input edges, this can ensure the smooth flow of information and avoid being blocked. In this type, the $\alpha_{ji}$ is updated by:

These two types will be further discussed in the experiments section. Algorithm 1 summarizes the optimization procedure detailedly.

Our optimization method is compatible with classical networks. To investigate the applicability, we select ResNet-CIFAR [10] consisted of $3\times 3$ conv and MobileNetV2-1.0 [31] consisted of Inverted Bottleneck. For the optimization of ResNets, we rewire the interval of $2$ in the BasicBlock to $1$ to form the complete graph. For MobileNetV2-1.0, each node involves a residual connection and can be viewed as a complete graph naturally. In the case that MobileNet owns fewer layers in each stage, we also increase the depth by increasing the node in each stage, resulting in larger search spaces. It is also a common skill to expand networks [38]. Through assigning learnable parameters to their edges, the topologies can be optimized using Algorithm 1. It should be mentioned that the additional computations and parameters introduced by the edges are negligible compared with convolution.

First, we evaluate the optimization of the connectivity with ResNets on CIFAR-100 [16]. The experiments are trained using $2$ GPUs ¹¹1All of our experiments were performed using NVIDIA Tesla V100 GPUs with our implementation in PyTorch [25]. with batchsize 128 and weight decay 5e-4. We follow the hyperparameter settings in paper [4], which initializes $\eta=0.1$ and divides by 5 times at 60th, 120th, 160th epochs. The training and test size is $32\times 32$. We report classification accuracy on the validation set by 5 repeat runs. The results are shown in Table 1. Under similar Params and FLOPs, the optimization brings $2.22\%$ improvement on Top-1 accuracy for ResNet-110, which reflects larger search spaces lead to more improvements.

Next, we extend our method to ImageNet dataset [30] using MobileNets. We train MobileNetV2 using $16$ GPUs for 200 epochs with a batch size of 1024. The initial learning rate is 0.4 and cosine shaped learning rate decay [22] is adopted. Following [31], we use a weight decay of 4e-5 and dropout [11] of 0.2. Nesterov momentum of $0.9$ without dampening is also used. The training and test size is $224\times 224$. The network with 2 times of layers is denoted as 2N. Under the mobile-setting, we achieve $76.4\%$ Top-1 accuracy. Under the larger optimization space of 6N, the optimization brings a $0.75\%$ improvement. This further demonstrates the benefits of topology optimization for different networks.

Due to restricted optional topologies of classical networks, the topology can be only optimized in small search spaces, which limits the representation ability of topology. These may limit the influence caused by topological changes and affect the search for optimal topology. In this section, we propose a larger search space, and fully illustrate the improvement brought by topology optimization. The properties of edges and nodes in the optimized topology are also analyzed.

We design a series of architectures named as TopoNets that can flexibly adjust search space, types of topology and node. As shown in Table 3, it consists of four stages with number of nodes of $\{N_{1},N_{2},N_{3},N_{4}\}$. The topology in each stage is defined by a graph, whose type can be chosen from {complete, random, residual}. The complete graph is used for the optimization of topology. For a more strict comparison, we also take the other two types as baselines. The residual one is a well-designed topology. In the random one, an edge between two nodes is linked with probability $p$, independent of all other nodes and edges. The higher the probability, the denser it is. We follow two simple design rules used in [10], (i) in each stage, the nodes have the same number of filters $C$; (ii) and if the feature map size is halved, the number of filters is doubled. The change of filters is implied by the first calculation node in each graph. For the head of the network, we use a single convolutional layer for simplicity. The network ends with a classifier composed of a global average pooling (GAP), a 1000-dimensional fully-connected layer and softmax function.

To evaluate the generalization and transferability for both optimization method and TopoNets, we also conduct experiments on COCO object detection task [19]. We adopt FPN [18] as the object detection method. The backbone is replaced with corresponding pretrained one in Table 4, and is fine-tuned on COCO train2017 dataset. We test using the COCO val2017 dataset. Our fine-tuning is based on $1\times$ setting of the publicly available Detectron [6]. The training configurations of different models are consistent. Test performances are given in Table 5. To comparable ResNet-50, TopoNets obtain significant promotions in AP with lower computation costs. Contrast with elegant residual topology, our optimization method can also achieve increase by $0.95\%$. These results indicate the effectiveness of the proposed network and the optimization method.

We further explore the properties of the optimized topology. First, we remove individual nodes according to its topological ordering in the graph and evaluate it without extra training. We expect them to break because dropping any layer drastically changes the input distribution of all subsequent layers. Surprisingly, most removals do not lead to a noticeable change as shown in Figure 4 (left). It can be explained that the available paths is reduced from $(n-1)!$ to $(n-2)!$, leaving sufficient paths. This suggests that each node in the complete graph do not strongly rely on others, although it is trained jointly. Direct links with input/output nodes make each node contribute to the final feature representation, and benefits the optimization process. Another observation is that nodes in the front of topological orderings contribute more. This can be explained that for a node with the ordering of $i$, the generated $x_{i}$ can be only received by node $j$ (where $j>i$). This causes the feature generated by the front nodes to participate in aggregation as a downstream input. It makes the front nodes contribute more, which can be used to reallocate calculation resources in future work.

Second, we consider the impact of edge removal. All edges with $\alpha$ below a threshold are pruned from the graph, only remaining the important connections. Accuracies before and after retraining are given in Figure 4 (right). Without retraining, accuracy decreases as the degree of pruning deepens. It is interesting to see that we have the “free lunch” of reducing less than $40\%$ without losing much accuracy. If we fix $\alpha$ of remaining edges and retrain the weights, it can maintain accuracy with $80\%$ of the nodes removed. This proves that the optimization process has found indeed important connections. After pruning edges, nodes with zero in-degree or zero out-degree maybe safely removed. It can be used to reduce the parameters and accelerate inference in practical applications.

We visualize the optimization process in Fig. 5. During the initial phase, there are strong connections between all nodes. As the optimization process progresses, the connections become sparse, leaving the critical ones. We sample topologies with different connectivity during the process and retrain them from scratch with $\boldsymbol{\alpha}$ froze. This allows us to compare the change of topology capabilities during optimization. Validation accuracies are given in the right of the figure. It can be seen the representation ability of connectivity increases with the training process, not just the weights of networks.