In Eq 1, is L_eval is a loss (where lower is better), it seems trivial to find sub-networks that perform less well than the original DNN. So I imagine L_eval is not a loss (as the L would suggest), but some performance metric where higher is better. Even in that case the problem is not fully defined, since F_i = F would satisfy Eq 1 while not being a useful solution.

We thank the reviewer for this valuable comment. Yes, the evaluation metric shown in Semantic DNN Subgraph Problem (SDSP) does not correspond to the loss function. We define it as the evaluation criterion used for scoring the network and its subgraphs on their respective datasets. In our work, we have chosen the evaluation metric as accuracy. We understand the confusion regarding the notation which would not arise if the property of the evaluation metric (higher value means better performance) was mentioned. We have updated the manuscript accordingly. We have changed the notation of the evaluation criterion to $\mathcal{B}_{eval}$ and added

A higher value of $\mathcal{B}_{eval}$ is assumed to correspond to better performance.

As mentioned in the comment, $\mathcal{F}_{\gamma_i} = \mathcal{F}$ would satisfy Equation 1. In our case, the problem definition would be more precise if we used the word proper subgraph. This would exclude the trivial solution and would solve the confusion. We have modified the problem statement to incorporate this discussion.

I find the writing of the paper very hard to follow. How are the semantic clusters built? I’m not sure I could follow the explanation in section 4 and algo 1, which is a bit too cluttered.

We are sorry that Section 4 and Algorithm 1 have been hard to follow. We have updated the manuscript and tried to make the steps easier to follow. We hope that it will clarify the questions that the reviewer might have regarding the procedure.

Something as important for the method as the Discriminative Capability Score is not actually explained anywhere.

Section 4 describes the procedure to obtain the discriminative capability score. The section builds up the intuition behind the discriminative capability score and describes it right before the equation 3. We have updated the manuscript to make it easy to follow the procedure and find the description.

Same issue with the training of the route predictor**

We have added more details to the Semantic Route Predictor subsection of Section 5 to illustrate the training of the semantic route predictor. Specifically, we add that

To train the auxiliary classifier $\boldsymbol{\chi}$, the section of the base model up to the $M-1$-th layer of $\mathcal{F}$ is frozen and the classifier is trained in supervised fashion using {$\mathbf{A}_{M-1}^j, \gamma_m^j$} , where j=1...|D| as the dataset.

Here, $\mathbf{A}_{M-1}^j$, and $\gamma_m^j$ are respectively the activation of the $M-1$-th layer of the base model and the ground truth semantic cluster for the j-th sample. As we are considering a pre-trained base DNN, we train the auxiliary classifier separately from the base network using the activations obtained from the $M-1$-th layer.

The authors claim to obtain SOTA results while using relatively old datasets and architectures. I don’t think such a choice invalidates the contribution, but I would weigh the claims accordingly.

We thank you for your comment. The setting we are proposing is new and it requires a score-based approach to select the filters in each layer to form the subgraph. As a result, we have chosen the [1], [2] for comparison as recent methods. Apart from that, we compare with the recent [3] which is a published work in ICLR 2023 to prove the efficacy of DCS as a pruning method. We are currently running SINF on ImageNet-1k and will report the results as soon as we obtain them.

[1] Sui, Y., Yin, M., Xie, Y., Phan, H., Aliari Zonouz, S. and Yuan, B., 2021. Chip: Channel independence-based pruning for compact neural networks. Advances in Neural Information Processing Systems, 34, pp.24604-24616. [2] Lin, M., Ji, R., Wang, Y., Zhang, Y., Zhang, B., Tian, Y. and Shao, L., 2020. Hrank: Filter pruning using high-rank feature map. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition (pp. 1529-1538). [3] Murti, C., Narshana, T. and Bhattacharyya, C., 2022, September. TVSPrune-Pruning Non-discriminative filters via Total Variation separability of intermediate representations without fine tuning. In The Eleventh International Conference on Learning Representations.

I thank the authors for their responses. I would like to clarify and follow up on some of the issues.

• Eq (1): I'm not sure writing "a proper subgraph" solves the issue. If I understand well an efficiency is the main objective, it would make more sense to aim at minimizing the number of nodes in each $\mathcal{F}_{\gamma_i}$ subject to Eq (1). I would suggest to revise Section 3 accordingly.
• Clarity: I apologize if my comment was unclear. I meant that DCS is not introduced as a high-level concept, and its connection to solving Eq (1) is not explained in an intuitive manner, with Algo. 1 being so cluttered it makes it very hard for a reader to understand the gist. I would strongly suggest the authors to revise the whole paper to allow for a better flow, such that every section/paragraph leads naturally to the following. Similarly, Fig 1 needs to be improved as per my comment in the previous round.

The authors start with a given layer $l$ and semantic cluster $\gamma_m$ (where up to this point, it is not clear if $\gamma_m$ comes from some ground truth information or is computed as the introduction suggested [...] the authors note that before deployment, the DCS is used to construct semantic subgraphs. Again is not yet clear how are the partitions obtained.

Thank you for your comment. In Section 3, we have stated that we assume that the $\gamma_m$ clusters are defined based on application-level similarities (e.g., classes related to flowers, insects, etc.) or pre-defined at the dataset level (e.g., as in the CIFAR100 dataset). In this case, the 20 superclasses in CIFAR100 form the semantic clusters we are considering. We are using this dataset to experiment on especially because it is pre-partitioned into semantic clusters. We have remarked this aspect in the updated manuscript we have submitted as part of the rebuttal.

For each data-point belonging to the semantic cluster, the activations for each feature map $A_{l,c_i}^j$ are computed and adaptive pooling is performed. Then, the feature map is flattened by the dependence on $l$ is gone.

We are sorry to see that the notation might have been confusing. Algorithm 1 is designed for a specific cluster and a specific layer and it is specifically mentioned in the algorithm heading. That is why the dependence on the layer and cluster is not explicitly mentioned for the feature vector and subsequent symbols. The dependence is maintained in the notation for the other quantities before so as not to disrupt the already defined quantities. However, we agree that keeping the dependence on the layer and semantic cluster can make it easier to follow the algorithm. We have made changes to reflect the dependence on layer and semantic cluster in the manuscript and we have reuploaded it for the reviewer’s convenience.

Moving on to the process of extracting the sub-graphs, we begin with $L$ and $M$, the last layer and the layer before the Common Feature Extractor. In this context, if $L$ is the last layer of (assuming) the backbone network, isn't $M$ also the layer of said network? In Fig.3 there is no illustration of what $L$ and $M$ since they backbone is not shown. The input is just passed through the common feature extractor and a sub-graph is selected without a corresponding backbone.

The $L$ and $M$ are part of the same backbone network. As defined in Section 3, we extract the sub-graph from a pre-trained network. For the sake of adaptive inference, we keep the first part as a common feature extractor and the rest of the network is used for the specialization for different semantic clusters. In this case, $L$ is the last layer of the backbone network and $M$ is the layer just before the common feature extractor from the end.

The first $l$ layers of the backbone network are frozen and used as the common feature extractor. The motivation is that the earlier layers of a DNN focus on features which overlap among multiple classes and possibly semantic clusters. From that perspective, $M$ would be the $l+1\ th$ layer of the back-bone and $L$ would be the last layer as mentioned. Through experimentation, we have found that at least the first 5 convolution layers are required to obtain a reasonable prediction accuracy on the semantic clusters for VGG16 and VGG19 and the first 2 layers are required for ResNet50. Therefore, the value of $M$ is 6 for VGG models and 22 for ResNet50. We have updated the manuscript clarifying the relation between the base DNN, the common feature extractor and the extracted sub-graph.

The authors note that "This procedure is performed for different values of $r_L$ and $r_M$. In this paper, $r_L$ is set between 90% and 10%, with steps of 10, while $r_M$ is set between 10% and 1%, with steps of 2". Why is this procedure performed? Is this some kind of initialization? What happens with the multiple different values? Do the authors select some kind of best performing model?

We thank the reviewer for pointing this out and we have fixed the notation in the updated version of the manuscript we have uploaded as part of the rebuttal.

The procedure of extracting sub-graph is performed for varying values of $r_L$ and $r_M$. This is because there can be multiple sub-graphs that satisfy our accuracy requirement. However, those sub-graphs will vary in their size and latency. By trying different values of $r_L$ and $r_M$, we can obtain several solutions satisfying our performance requirement and choose the optimum one based on additional requirements, for example, sub-graph size, latency. In other words, we are selecting the best performing DNN.

Regarding Weakness 1

There are many quantization and pruning approaches that can speed up the inference without fine-tuning or retraining. Can do more comparison experiments with SINF and show the comparable results of the whole pipeline.

We thank you for your comment. To the best of our knowledge, the previous work that does not require fine tuning is very limited -- we were only able to find [1] as a recent paper that does not require fine-tuning. We would be happy to compare against other non fine-tuning techniques if the reviewer shared these papers with us. We would like to clarify that we are not considering pruning at train-time or retraining approaches. We are assuming that we start with a pre-trained DNN and extract the sub-graphs corresponding to the semantic clusters defined by the task at hand.

For the extraction of the sub-graph part, we have compared against metrics which are usable in our scenario. For the pruning part, we are considering the most recent work closest to our setting for comparison. Notwithstanding, we point out that designing a pruning algorithm is out of the scope of this paper. Our goal is to design a dynamic DNN which can immediately adapt to changing requirements. For this reason, we cannot fine-tune the DNN at run time.

Regarding quantization, as pointed out in the background section (Section II), we believe our proposed work is orthogonal to that approach and can be used on top of quantization and coding approaches to further improve the performance.

[1] Murti, C., Narshana, T. and Bhattacharyya, C., 2022, September. TVSPrune-Pruning Non-discriminative filters via Total Variation separability of intermediate representations without fine tuning. In The Eleventh International Conference on Learning Representations.

Regarding Weakness 2

Table 1 lacks the results of ResNet50 on CIFAR100.

Thank you for pointing this out. We are comparing our approach to the work which has been published in the last ICLR 2023 [1] . To make a fair comparison, we are using the same DNN model as in [1]. Since the work does not provide any performance result for ResNet50 on CIFAR100, we are not comparing for the same.

Regarding Weakness 3

Lack the analysis of the poor improvement in Table 1, where there is almost no improvement for VGG19 on CIFAR100 and only a slight improvement on CIFAR10.

We thank you for the opportunity to clarify this point. A possible explanation is that since both our technique and the state of the art IterTVSPrune have pruned a significant amount of weights – respectively about 50% and 60% for CIFAR10 and CIFAR 100% – the DNN has reached a lower bound on its predictive capability. In other words, this means that the DNN cannot be pruned more without compromising the accuracy. In the other DNNs (VGG16 and ResNet50) the amounts of weights pruned is less aggressive (up to 40% for VGG16 and up to 35% for ResNet50) so eventually there could be room for improvement. This aspect is nevertheless intriguing and we plan to delve deeper into this aspect in future work. We will include these discussions in the final manuscript.

Regarding the Question

Is there any proof or metric to evaluate the intrinsic redundancy in latent representations?

In Section 3, we have used $L_1$ distance to quantify the similarity of the filter response for inputs of two different classes (otter and seal). We have also utilized the overlapping between filter activation for two classes to quantify this similarity. Although these metrics do not exactly quantify the intrinsic redundancy, it is part of our current work to characterize the redundancy in a more formal manner.

Regarding Weakness 1

There are a lot of existing pruning methods, e.g., DepGraph: Towards Any Structural Pruning but this paper does not provide any comparison to existing works.**

We thank the reviewer for this comment. Although the end goal of pruning and our proposed approach is to decrease the computational burden of mobile devices related to executing deep neural networks (DNNs), the primary objective of our work is to do so without the need to fine-tune the DNN, as in real-world mobile systems the DNN has to be adapted immediately to changing requirements.

The first key reason behind this choice is that fine-tuning DNNs takes a significant amount of time. For example, fine-tuning one of our sub-graphs even for 20 epochs takes on average a minute, which is just for CIFAR-100. For 20 sub-graphs corresponding to 20 semantic clusters, it takes about 20 minutes. In real-world dynamic mobile scenarios where priorities might change, it may be infeasible and energy-expensive to continuously fine-tune the model. For example, if we are deploying a drone for surveillance in a mountain area, that would encounter certain classes (e.g., animals). However, if the UAV operates in an urban area, then it would require a different set of classes (e.g., cars). Given the dynamic nature of the system, allowing fast switching becomes a compelling necessity.

Another reason is that fine-tuning the DNNs for one set of classes can degrade its performance in other tasks due to catastrophic forgetting [1,2]. Conversely, our approach is to pre-compute and then select at runtime the sub-graph with the capability of achieving sufficient accuracy on the given set of semantic classes.

DepGraph and many other pruning approaches rely on fine-tuning to improve performance. For this reason, we compare to the most recent work for pruning which adopts same scenario as ours [3] in Table 1. We also compare the proposed discriminative capability score (DCS) with other score-based metrics usually used for pruning in Figure 4.

[1] Pomponi, J., Scardapane, S. and Uncini, A., 2022. Centroids Matching: an efficient Continual Learning approach operating in the embedding space. Transactions on Machine Learning Research. [2] Davari, M., Asadi, N., Mudur, S., Aljundi, R. and Belilovsky, E., 2022. Probing representation forgetting in supervised and unsupervised continual learning. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (pp. 16712-16721). [3] Murti, C., Narshana, T. and Bhattacharyya, C., 2022, September. TVSPrune-Pruning Non-discriminative filters via Total Variation separability of intermediate representations without fine tuning. In The Eleventh International Conference on Learning Representations.

Regarding Weakness 2

The acceleration on CIFAR10/CIFAR100 is not satisfied. For example, DepGraph achieves an 8.92× acceleration with a 3.11 loss in accuracy on CIFAR100 with VGG19. However, the results provided by the author (~1.72x and 2.83 loss on acc) are worse than previous work.

Although the review is correct, we point out that conversely from DepGraph and other pruning approaches in literature, our results are obtained without fine-tuning. When considering the DCS score for pruning, and enabling fine-tuning, our proposed DCS strategy achieves 9.08x speed up for only 3.27% loss in accuracy which is comparable to DepGraph.

Regarding Weakness 3

The writing is confusing, it is hard to find the main results.

We are sorry to know that the reviewer has found the writing to be confusing and main results hard to find. We have updated the manuscript and tried to highlight the main results. We hope that it will make it the results easier to find.