Neural Sculpting: Uncovering hierarchically modular task structure in neural networks through pruning and network analysis
Authors: Shreyas Malakarjun Patil
Loizos Michael
Constantine Dovrolis
Venue: NeurIPS 2023 poster (2023)
Keywords: Neural networks
Hierarchical modularity
Pruning
Sparsity
TL;DR: In this work, we present an approach that utilizes both neural network unit and edge pruning techniques, as well as a network analysis tool, to reveal the previously unknown hierarchical modularity underlying a given task.

Abstract: Natural target functions and tasks typically exhibit hierarchical modularity -- they can be broken down into simpler sub-functions that are organized in a hierarchy. Such sub-functions have two important features: they have a distinct set of inputs (input-separability) and they are reused as inputs higher in the hierarchy (reusability). Previous studies have established that hierarchically modular neural networks, which are inherently sparse, offer benefits such as learning efficiency, generalization, multi-task learning, and transfer. However, identifying the underlying sub-functions and their hierarchical structure for a given task can be challenging. The high-level question in this work is: if we learn a task using a sufficiently deep neural network, how can we uncover the underlying hierarchy of sub-functions in that task? As a starting point, we examine the domain of Boolean functions, where it is easier to determine whether a task is hierarchically modular. We propose an approach based on iterative unit and edge pruning (during training), combined with network analysis for module detection and hierarchy inference. Finally, we demonstrate that this method can uncover the hierarchical modularity of a wide range of Boolean functions and two vision tasks based on the MNIST digits dataset.

Neural Sculpting: Uncovering hierarchically modular task structure in neural networks through pruning and network analysis
Loizos Michael Constantine Dovrolis 1 Georgia Institute of Technology, Atlanta, USA "Open University of Cyprus, Nicosia, Cyprus CYENS Center of Excellence, Nicosia, Cyprus "The Cyprus Institute, Nicosia, Cyprus am._pati@ggatechcommm edu, loizos@ouc. ac cy, c. cdoovoliss@ci..ac.
Shreyas Malakarjun Patil
Abstract
Natural target functions and tasks typically exhibit hierarchical modularity they can be broken down into simpler sub-functions that are organized in a hierarchy. Such fo-ffucctions have two important features: they have distinct set of inputs (input-eeurrabilit) and they are reused as inputs higher the hierarchy (reusabil- dy). Previous studies have established that hierarchically modular neural networks, which are inherently sparse, offer benefits such as learning efficiency, general- ization, multi-task learning, and transfer. However, identifying the underlying sub-functions and their hicrarchical structure for given task can be challenging. The high-level question in this work is: if we Iearn task using sufficiently deep neural network, how can we uncover the underlying hierarchy of sub-functions that task? As starting point, examine the domain of Boolean functions, where it is easier to determine whether a task is bierarchically modular. We propose an approach based iterative unit and edge pruning (during training). combined with network analysis for module detection and hierarchy inference. Finally, we demonstrate that this method uncover the hierarchical modularity of wide range of Boolean functions and two vision tasks based on the MNIST digits dataset.
1 Introduction
Modular tasks typically consist of smaller sub- functions that operate on distinct input modalities, such as visual, auditory, or haptic inputs. Additionally, modular tasks are often hierarchical, with simpler sub-functions embedded in, or reused by, more complex functions [1]. Consequently, hierarchical modularity is a key organizing principle studied in both engineering and biological systems. In neuroscience, the hierarchical modularity of the brain's 's neural circuits is believed to play a crucial role in its ability to process information efficiently and adaptively [2, 3, 4, 5). Translating this hierarchical modularity to artificial neural networks (NNs) can potentially lead to more efficient, adaptable and interpretable learning systems. Prior works have already shown that modular NNs efficiently adapt to new tasks [6, 7, 8] and display superior generalization over standard NNs [9. 10, 11]. However, those studies assume knowledge of the task's 's hierarchy, or hand-design, modular NNs at initialization. Given arbitrary task, however, normally do not know its underlying nubffunctions or their hierarchical organization. The high-level question in this work is: we learn a task using a sufficiently deep NN, how we uncover the underlying hierarchical organization of sub fub-functions in that task?
Recent studies through NN unit clustering have demonstrated that certain modular structures can emerge during the training of NNs [12, 13, 14, 15, 16). However, it is unclear whether the structures extracted reflect the underlying hierarchy of sub-functions in a task. Csordas et al. [17] proposed a method that identifies sub-networks in NNs that learn specific sub-functions. This method however,
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

requires knowledge of the exact sub- fubbffnctions within a task's s hierarchy. Ideally, modules correspond- ing to specific funbffuntiios should emerge through training strategy, and a method should be available to detect these modules without explicit knowledge of the corresponding sub-functions.
Biological networks exhibit hierarchical modularity where clusters of nodes with relatively dense internal connectivity and sparse external connectivity learn specific sub-functions [4, 5, 18, 19]. Drawing inspiration from this, we propose Neural Sculpting, a novel approach train and structurally organize NN units to reveal the underlying hierarchy of sub-functions in a task. Within a hierarchically modular task, we consider sub-functions that are seput-separable and reused. We first show that conventionally trained NNs do not acquire structural properties that reflect the previous cub-function properties. To address this, we introduce a sequential unit and edge pruning method to train NNs. Unit pruning first conditions the NN to learn reused sub- sub-functions, while edge pruning subsequently reveals the sparse connectivity between the learned sub-functions. Finally, we propose a network analysis tool to uncover modules and their hierarchical organization within the sparse NNs.
We demonstrate the capability of Neural Sculpting to reveal the structure of diverse hierarchically modular Boolean tasks and two MNIST digits based tasks. To the best of our knowledge, this paper is the first to analyze specific sub-function properties within hierarchically modular task and propose an end-to-end methodology to uncover its structure. This work also sheds light on the potential of pruning methods to uncover and harness structural properties in NNs.
1.1 Preliminary
To represent the decomposition of task, we visualize it as graph. Initially, we consider Boolean functions and their corresponding function graphs. A Boolean function ff 10" + input bits to m output bits. We define the set of gates G as {A, v, where A represents logical conjunction (AND), V represents logical disjunction (OR), and represents the identity function (ID). Additionally, we define the set of edge-types E as { }}. where + represents transfer edge and represents a negation edge.
10",, maps
A (G, F)-graph representing a Boolean function f (0. - (0. 1 t is directed acyelic graph comprising: n sequentially ordered vertices with zero in-degree, designated as the input nodes; k vertices with non-zero in-degree, designated as the gate nodes, with each vertex associated with a gate in G and each of its in-edges associated with an edge-type in E; and m sequentially-ordered vertices with zero out-degree, designated as the output nodes.
Function Graph:
We use the G and E defined above, as NN units have been demonstrated learn these universal gates [20]. Function graphs, which break down complex computations into simpler ones, are typically sparse. Modularity in sparse graphs refers to the structural organization of subsets of nodes that exhibit strong internal and weak external connectivity, which are grouped into modules.
Sub-function: A sub-function is subset of nodes within the function graph that collectively perform a specific task. The sub-function is characterized by having strong internal connectivity within its nodes, meaning that they are highly interdependent and work together achieve the desired output. At the same time, nodes in the sub-function have weak external connectivity, indicating that they are relatively independent from the rest of the graph.
Input Separable: Two sub-functions are considered input separable if their in-edges originate from distinct and non-overlapping subsets of nodes in the function graph.
Reused: sub-function is reused if it has two or more outgoing edges in the function graph.
Training NNs on target Boolean functions: We start by obtaining the truth table of each function graph, which serves our data source. The training set ;x,,,')) includes the complete truth table with added random noise (A(0, 0.1)) during each iteration to increase the number of training samples. The validation set (X..,
.., ..)) consists of the noise-free rows of the truth table. We use multi-layered perceptrons (MLPs) with ReLU activation for the hidden units and Kaiming weight initialization to learn the Boolean functions. The loss function is bitwise cross-entropy with Sigmoid activation. The NNs are trained using Adam optimizer with L2 regularization of 1e 4.
Distinction between function reuse and operation reuse. Consider the AND gate which an operation that is independent of its input variables. On the other hand, a sub-function is a combination of such operations along with specific inputs. Specific operations have to be relearned if applied to different inputs due to the fixed data flow in NNs [17].
2

---

2 Standard training of NNs is not enough
We show that NNs through standard training, do not acquire structural properties that reflect the properties of sub-functions. Specifically, we consider the two properties in isolation by constructing two graphs: one with input separable sub-functions, and the other with a reused sub-function.
2.1 Input Separable
The first function graph we consider has 4 input nodes and 4 output nodes. The output nodes {y1, 32) depend only on {21, 22), while the output nodes {ya: y4 depend only on {I3, x4} (Figure la). We train various NN architectures to learn the target function with perfect accu- racy on the validation set. The property of the function graph that reflects input separale sub-functions is that there are paths from input nodes }2) to output nodes {y3, y4) and from input nodes { output nodes {y1, 92)- However, in a neural network, all input units are connected through the same number of paths. Therefore, we analyze the strength of their learned relationship by considering the product of weight magnitudes along those paths.
Input separable sub- functions
page Hught Product patee Seroe 1M
500.07
135.00
341.03
113.27
V97 82
799.50
624
1000.25
040 64
065.00
AND Trandy Nop
Loudide (100)
1-ter 0190
Figure I: a. Function graph with input separa- ble sub-function, b. Edge-weight product of paths from input units to output units in a trained NN.
all output units
Consider a trained NN parametrized by 0 E IR" and the set of all paths, P. Each edge weight 6, is assigned a binary variable to indicate whether it belongs to a given path p E P. We define the edge-weight product of path as n = -1==1 10_).
Width
24
36
48
Hidden Layers
and (i, = Σpe PppP... Tp represents the sum of F for all paths from input unit i to output unit j. We evaluate π (i, for i = 1, 2 and j = 3, 4, and (i. for i = 1,2 2 and j = 1.2. If the former is significantly smaller than the latter, then the input units 1 and 2 are not used by output units and 4.
1
2
x
x
X
3
x
x
X
Table 1: NN architectures with vary- ing widths and depths for which both null hypotheses are rejected.
We perform two-sample mean test with unknown standard deviations, with (1) representing the mean and sample standard deviation of ((., for i = 1,2 and j 3, 4, and (12, 82) representing the mean and sample standard deviation
of T (i.j) f = 1, 2 and j 2. The null hypothesis Ho is μu μ2, and the alternative hypothesis is 141 < U12. A similar test is performed for input units 3 and 4. Figure 1b shows an example heat map for π (i.j), where i.j 2,, 3, 4). For the example shown we cannot reject the null hypotheses. Similarly, we conducted statistical tests on nine different NNs with varying architectures and seed values, and the results are summarized in Table 1. For NNs with a single hidden layer, the null hypotheses, but for deeper NNs, both the null hypotheses cannot be rejected.
reject
2.2 Reused
Consider the function graph shown in Figure 2a, consisting of 4 input nodes and 16 output nodes. First, we construct an intermediate sub-function g(X) such that the three gate nodes depend on all the inputs. This sub-function is utilized by two separate gates, fi (g) and fe(g), which are then used 8 times by different output nodes. All paths to the output nodes pass through three gate nodes in the first hierarchical level and two gate nodes in the second. We analyze the edge- weight product of the paths from hidden units to output units. Let T. denote the sum of Tp for all paths originating from hidden layer which contains N; hidden units. We compute
Reused sub-function
cdgo anttee prod
Hellen Heden Lager 2
Sugatics
Figure 2: a. Function graph with reused sub- function, b. the number of units covering 90% of the total edge-weight product of paths.
3

---

the minimum number of units, Nyp that are necessary to achieve P% of the total T.. By comparing Nyp to that of the function graph, we can conclude whether the NN has learned the reused states,
We independently trained NNs with two hidden layers and different widths on the target Boolean function. The resulting No values for different layers are shown in Figure 2b. Our analysis indicates that, as the width of the NN increases, so does Ngo in both the hidden layers, and these values are consistently close to the actual width of the NN. We trained an NN with hidden layers of width 3 and 2, respectively, to confirm that NNs with those widths can learn the function well.
3 Iterative pruning of NNs
In the previous section, demonstrated that standard NN training is inadequate for learning structural properties that reveal input separable or reused sub-functions. Nevertheless, we observed that NNs with a relatively low number of parameters could still acquire these properties. Since hierarchical modularity is a property of sparse networks, we explored NN pruning algorithms as a means of achieving this sparsity. Prior research has shown that pruning NNs can reduce their number of parameters without compromising their performance [21, 22, 231. Edge pruning methods typically require specifying& a target NN density or pruning ratio [21, 24). but determining density value that preserves the NN's performance remains an open question. Recently, iterative magnitude pruning [25, 26] has emerged as a natural solution to this problem. The algorithm prunes edges iteratively, removing some edges in each iteration and then retraining the NN. This process can be repeated until the NN achieves the same validation performance as the dense NN while being as sparse as possible.
3.1 Iterative edge pruning
Consider the initial edge pruning step Pa- We train the dense NN and prune % of the edges with the lowest weight magnitude. The sparse NN resulting from this pruning is then trained with the same number of epochs and learning rate schedule as the original NN. We repeat this process until the sparse NN can no longer achieve the same validation accuracy as the dense NN. At this point, we rewind the NN to the previous sparse NN that achieved the same validation accuracy as the dense NN and update the value of Pe as Pe
Edge Weiget palt edge poused
tnitur di,
Namber of undt Fur 50% copp migght prodict
My thet
0.50
5.00
Hiddon Logar wil toem
2e/2. We repeat this process until P= becomes lower than the required step to prune a single edge, thereby ensur- ing that the lowest possible density is achieved.
56.75
56.70
0.20
3.00
0:00
0.02
12
72.42
We next apply the tests developed in the previous section to analyze whether edge-pruned NNs acquire structural properties resembling those of the sub- functions. Specifically, we train and prune different NN architectures to learn the function graph with For the example shown in Figure 3a, as well as for NNs with different architectures, we can reject the null hypotheses in favor of the alternate hypotheses. This implies that edge-pruned NNs acquire structural properties that enable them to recognize input-separable sub-functions.
Figure 3: a. rdge-weight product of paths from input units to output units in edge-pruned NN; b. the number of units covering 90% the total edge-weight product of paths in edge-pruned NNs.
sub-functions
Consider the previous function graph that has reused sub-functions and NNs with increasing widths. We independently train and prune each NN architecture and determine the number of units Ngo (Figure 3b). We find that in a majority of the trials, N2 = 2. which are reused by the output units. Although there is a significant reduction Ngo, the edge-pruned NNs fail to identify units that are being reused. We observe that those units. However, they do not identify units corresponding to sub-functions that are not sparsely connected yet reused. We hypothesize that this may be due to the initial pruning iterations where some edges from all units are removed, leaving no hidden units with dense connectivity to learn densely connected and reused sub-function Additionally, this could also be due to very large NN widths and the absence of an objective conditioning NNs to utilize as few hidden units as possible. Therefore, next we introduce an iterative unit pruning method to limit the number of units used.
NNs identify sparse connectivity between units and reuse

---

3.2 Iterative hidden unit pruning
To prune hidden units, we first train the neural network and then assign each hidden unit score. We eliminate % of the hidden units with the lowest scores and train the resulting pruned network for the same number of epochs and learning rate schedule as the original network. We repeat this two-step pruning process iteratively.
We use loss sensitivity the scoring metric for the units [27, 28, 29,30] 30], which approximates the change the network's loss when the activation of a particular hidden unit is set to zero. Specifically, for a unit i in hidden layer I, with activation a, the score is computed a
aC(DD. v. 0) S
of
da
The iterative unit pruning process continues until the NN can no longer achieve the same validation accuracy as the original NN. To ensure that have pruned as many units possible, we revert to the latest NN that achieved the same validation accuracy as the original NN and halve the value of pu-
This process is repeated until the unit pruning step becomes lower than the step
Produc unbeddee
size needed to prune single unit. We
that farm LOs edeg gtearoduz
perform unit pruning before the edge
pruning process to identify the mini-
mum widths required in each hidden layer. Once the minimum widths are de- termined, edges are pruned to reveal the sparse connectivity between those units. For additional details please refer to ap- pendix section
0:00
0.03
10.32
00.33
1101
1800e Lager
U-tariit 23 31 03
10V with
Figure 4: a. Edge-weight product of paths from input units to output units in unit-edge pruned NN; b. the number of units covering 90% of the total edge-weight product of paths in unit-edge pruned NNs.
We conducted the previous tests to ana- lyze whether the unit-edge pruned NNs acquire structural properties resembling those of the sub-functions, as presented in the previous section. The results of these tests shown in Figure 4, and show that the unit-edge pruned NNs do acquire structural properties resembling both input separable sub-functions and reused sub-functions.
A. Pruned NN
B. Layerwise unit clustering
C. Sequential merging of clusters
BI. Outgoing connectivity
B2. Clasess laya:
Clastcing exppu
Cl.Cormantsty work
Merged layan
C). denare
Figure 5: Proposed module detection pipeline.
4 Detecting modules within sparse NNs
In this section, we propose a method to uncover sub-networks or modules that approximate the sub-functions within the target function. We approach this by projecting the problem as two-step partitioning problem due to the layered structure of NNs. First, we cluster the units belonging to the same layer. We assume that given layer, there exist various subsets of units that participate in learning the same sub-function. Next, we merge the previous unit clusters across layers such that they exhibit strong connectivity. The overview of our proposed method is illustrated in Figure 5.
Let us consider single layer with Nj units. For each unit, we construct feature vector based its outgoing connectivity. The feature vector for unit i is a binary vector f! E {0, 13,,, where is the total number of units all the later layers. unit j is connected to unit through at least one directed path, then O') = 1, otherwise f(() = O. Our hypothesis that the units that participate in learning the same sub-function are reused by similar units in the later layers. To partition the units into clusters such that their feature vectors have low intra-cluster and high inter-cluster distances, we use the Agglomerative clustering method with cosine distance and
Layer-wise unit clustering:
5

---

average linkage. To identify the optimal number of clusters K2, we use the modularity metric, which we have modified for our problem [31, 32, 33].
Let D be the normalized distance matrix of the unit fea- ture vectors, where the sum of all elements is equal to 1. Consider the units partitioned into k clusters and a matrix A E R where Aij Laec, Dab represents the sum of the distances between all pairs of units in clusters C; and Cj. The modularity metric, denoted by M, measures the quality of the partitioning and defined as:
2
M
Σ i=1
Aa
Σ
Aij
(2)
The first term this equation measures the total intra-cluster distance between the unit features while the second term is the expected intra-cluster distance under the null hypothesis that unit distances randomly assigned based joint probabilities in D. negative value of M indicates that pair-wise distance within a cluster is lower than the random baseline. We iterate through values ranging from 2 N₂ 1, which obtained through Agglomerative clustering, and select the value of k that minimizes the modularity metric.
The modularity metric can accurately detect the presence of multiple unit clusters (Ki - 2, ..., Ni 1). However, it fails for the edge cases where all units may belong to a single cluster (K₃ = 1) or to separate individual clusters (K₃ Ni). To address those, we conduct separability test if the modularity metric is lowest for k = 2 or N₁ 1, or the modularity metric values are close zero. Modularity metric close significantly different from the random baseline. To determine this, we set a threshold on the lowest modularity value obtained.
is indicator that the intra-cluster distances are not
The unit separability test is designed to evaluate whether two units a cluster can be separated into sub-clusters. Consider two units and j. with o; Σ S. og Σ> neighbors respectively, and oi f @ fJ common neighbors. We consider random baseline that preserves o and oj. The number of common neighbors is modeled as binomial random variable with g trials and probability of success p x The units separable if the observed value of oi is less than the expected value E((;y) under the random model.
Separability test:
Consider the partition where N; - 1 clusters are obtained. the two units that are found in the same cluster are separable, it implies that all units belong to separate clusters. Now let us consider the partition of units into two clusters. We merge the feature vectors of the two unit groups. If the two groups of units are not separable, it implies that all units must belong to the same cluster. In some cases, both tests yield positive results. We determine the optimal number of clusters by selecting the result that is more statistically significant.
Merging clusters across layers: Strongly connected clusters from adjacent layers are next merged to uncover multi-layere modules. Consider, Cj í 1,2, K, to be the clusters identified at layer 1. Let el, be the number of edges from cluster Ct to cluster C/+1- The two clusters are merged if cl
2 8m and EE
Ki 2 Sms where 8m is the merging threshold.
The output units are merged with the previous layer's modules, ensuring that om fraction of incoming edges to the unit are from that module. This allows multiple output units to matched to the same structural module.
soparable sub function
Reused sub function GOO
Isput separable reused
Single sub-finction
2999
Negation
Figure Function graphs used to validate the proposed pipeline

---

Experiments and Results
5.1 Modular and hierarchical Boolean function graphs
In this section, we conduct experiments on Boolean function graphs with different sub-function properties to validate our pipeline. We begin by testing the pipeline on four function graphs shown Figure 6. These graphs include: input sep- arable sub-functions, 2) a reused sub-function, 3) sub-functions that are both input separable and reused, and function graph without any such sub-function where all nodes are strongly connected every other node.
Success rate. uncovering modules
corresponding to subb-functions
22
hidden layer
hidden layers
We perform 36 trials for each function graph by training neural networks with combinations of 3 width values, 3 depth val- ues, and 4 seed values. A trial is considered successful if the proposed pipeline detects module corresponding an input separable or reused sub-function (Figure 5). For Boolean func- tions, we the modularity metric threshold to -0.2 and the cluster merging threshold to 0.9. Figure shows the success rates for each function graph and NNs with different depths. We observed that the proposed pruning and module detection pipeline has high success rate when the depth of the NN exceeds that of the function graph. (see to appendix section for NN visualizations)
layers
00
input separable
reused
both
Figure 7: Success rates for the val- idation function graphs
5.2 Sub-functions that are reused many times are uncovered accurately
We consider the function graph shown Figure 6b, which contains a single reused sub-function. We vary the number of times the two intermediate gate nodes in the second hierarchical level used by decreasing the number of output nodes and measure the success rate. The results are shown in Figure 8, as the
Success rate reused sub-funcion
1.
where we observe an increasing trend in the success number of output nodes using the two gate nodes increases. As the number of output units using the two gate nodes decreases, learning the two gate nodes using the previous "dense" sub- function may not be efficient. We provide visualizations of the corresponding NNs in the appendix section C. Note that NNs with only one hidden layer recover a single module, as the function graphs require four hierarchical levels. If only three hierarchical levels are available, the function graph collapses to dense graph.
hidden layor
hidden
hidden layars
Number of times used
Figure 8: Success when the number of times a sub-function is used increases
OR
AND
ID
Transfer
Negation
Figure 9: Increasing the input overlap (reuse) between input separable sub-functions
5.3 Sub-functions with higher input separability are detected more accurately
In this experiment, we consider function graph with two input separable sub-functions shown in Figure 9a. We increase the overlap between the two separable input sets by decreasing the total number of input nodes and reusing them. We also vary the number of times each sub-function is replicated or used in the output nodes. Our goal is to uncover three properties of the structure: accurately separated input units into sub-function specific and reused, two output sub-functions accurately detected in later layers, and all hidden units belong to either of the two output modules. The success rate for each these properties as function of input overlap and sub-function use shown in Figure 10.

---

reparabilly
Sacconss rate: Outpur sut funchon
1.00
2.00
1,00
1.50
1,50
1.0
1.00
10
1.00
1.00
1.00
3,00
0.90
1.00
1.00
1.00
1,00
C09
0:57
1.30
1,00
1.00
0.64
0.03
0.50
C15
9-31
01.00
0:09
0.67
12
1.1
0:5
0.5
006
0.25
0:33
0.63
665
Number
Numbor uoed
Numbbr time Lood
Figure 10: Success rates for various properties uncovered by the pipeline when the input overlap between two sub-functions is increased
We observe that our method has a high success rate for detecting these properties for sub-functions with high imput separability. However, as the overlap between input node sets increases, the success rate for detecting imput modules decreases, Furthermore, the success rate decreases as the number of times a sub-function is used decreases. We also observe that for sub-functions with low input separability (and high input overlap), intermediate units are often clustered into a single module due the hidden units pruning step. Finally, we find that the same trend is observed for detecting output sub-functions, where increasing input overlap and decreasing sub-fune functuntioon use results in low success rate for our method. (See appendix section D for visualization of these results).
Hicrarchical Lovels
5 Hicrarchical Levels
Hicrarchical Levels
OR
AND
ID
Transfer
Negation
Figure 11: The same Boolean function represented by different function graphs depending the number hierarchical levels
5.4 Hierarchical structures uncovered vary depending on NN depth
The function graph in Figure la consists of two input separable sub-functions, the output those sub-functions is then used by a single intermediate sub-function. This intermediate sub-function is then reused by two additional sub-functions to produce final output. Interestingly, we observe that the proposed pipeline uncovers different hierarchical structures depending the depth of the NN.
Figure 12a shows the success rate of uncovering the specific sub- functions segregated by the NN depth. We find that NNs with depth greater than or equal to the number of hierarchical levels (5) can uncover three types of sub-functions in the function graph. However, for NNs with
Success uncowenig
Rucomes rale: dettccing medille Wki hierarchica
connespandnng lust--cnntiions
Success rate
13
2 dden byyers in dden layeru
Ticken layers
didienn
lower depth, only the input sepa- rable sub-functions are uncovered, while the intermediate and output sub-functions are merged into a sin- gle module.
Ingue
smngle
culput
Number
Figure 12: Success rates: a. uncovering specific sub-functions, b. uncovering the overall hierarchical structure, for NNs with varying depths trained on function graph in Figure 11
This result highlights the importance selecting an appropriate depth for the NN architecture to effectively uncover hierarchical structures in Boolean function graphs. (see appendix section E for NN visualizations) In addition, we report the success rates of uncovering the exact hierarchical structure that corresponds to the depth of the NN as vary the number of times the output sub- fobnfunntions

---

were used (Figure 12b). The findings demonstrate an increasing trend in the success rate, which is consistent with our previous results.
5.5 Modular and hierarchical functions with MNIST digits
In this section, we present an experimental evaluation of hierarchically modular tasks constructed using the MNIST handwritten digits dataset. We set the modularity metric threshold to -0.3 and the cluster merging threshold to 0.6 for tasks with MNIST digits.
Classifying two MNIST digits: We begin by considering a simple function constructed to classify two MNIST digits. The NN is presented with two images concatenated together, and the output is vector of length 20. The first 10 indices of the output predict the class for the first image, and the remaining 10 predict the class for the second image. We construct the dataset such that each unique combination of labels has 1000 input data points generated by randomly selecting images. We split the data into training and validation sets with an 8:2 ratio, and then train nine neural networks with varying widths (392, 784, 1568) and number of hidden layers (2, 3, 4) to learn the function for four different seed values. We use Adam optimizer with bit-wise cross-entropy as the loss function, and select 99% as the accuracy threshold for the pruning algorithm, as all dense NNs achieve at least 99% validation accuracy. Out of the 36 trials conducted, we obtain two completely separable modules for 33 out of 36 trials, indicating the high effectiveness of our approach. (see appendix F for NN visualizations)
Hierarchical and Modular MNIST Task: We consider next a hierarchical and modular task that uses the MNIST digits dataset (Figure 13a). The task takes two MNIST images input, each belonging to the first 8 classes (digits 0-7). The digit values are represented as 3-bit binary vectors and used construct three output Boolean sub-functions. To generate the dataset, randomly select 1000 input data points for each unique combination of digits. The data then split into training and validation sets with an 8:2 ratio. All the NNs that experiment with reach a validation accuracy of 98%, which we use as the accuracy threshold for the pruning algorithm.
To analyze the modular structure uncovered by methodology, we divide the success rates into three categories: (1) detecting two input separable modules, (2) detecting three output modules, and (3) mid- dle layer seprabiparyyility into ei- ther the input separable modules the output separable modules. We observe that the NNs uncover the three output modules with high suc- cess rates. However, for NNs with lower depths, the NNs fail to re- cover the two input separable mod- ules, and all the units in the early layers are clustered into a single module. As the depth of the NN increases, we find that the input separable modules are recov- ered with high accuracy as well. We observe that the success rates for middle layer unit-separability are very low, even when the depth of the NN increases. The units belonging to those hidden layers are often clustered into single module. These units may be learning representations required to approximate the two digits well. This finding indicates that the NN depths experiment with may not be sufficient to capture the underlying function, despite the NNs learning the task with high validation accuracy. Please refer to appendix F for NN visualizations.
Success rates: Hicrarchical task
0.0
Success
66
6 4
Input separable sub-function
Output sub-functions
Middle layers separability
AND Truafer Nogaton
Number of hidden layers
Figure 13: a. Hierarchically modular task constructed with MNIST digits; b. Success rates for various modules recovered by NNs with varying depths.
Related work
Emerging modular structures trained NNs has been subject of prior investigation, primarily through unit clustering algorithms. Previous methods for extracting such structures can be categorized

---

as either structural or functional. Structural methods organize units based on their structural charac- teristics, including connectivity and edge-weights [12. 13, 14]. while functional methods consider attributes based on unit activation patterns [15, 16]. However, it remains unclear whether these extracted structures represent the underlying hierarchy of sub-functions in a given task.
To the best of our knowledge, this work is the first attempt to introduce an approach that combines training (pruning) and network analysis to unveil the hierarchical modularity of tasks. Our proposed method for clustering units and discovering modules aligns with the structural methods. A series of prior studies leveraged normalized spectral clustering to globally extract unit clusters and analyze their characteristics [14, 15]. Spectral clustering optimizes for N-cuts, quantifying the internal connectivity relative to the external connectivity of unit clusters. Our method is most similar to previously introduced layer-wise unit clustering techniques [12. 13J. These methods consider incoming and outgoing edge-weights to group units within a layer and consolidate edges into single incoming and outgoing connections. Importantly, all previous methods were tailored for conventionally trained NNs. contrast, our approach is simpler and customized for the pruned NNs we obtain.
Pruning of NN units and edges has gained significant traction as a method to enhance NN computational efficiency and reduce memory demands while maintaining performance integrity [21, 24, 23, 34, 35, 30, 36, 37, 38). Recent research has also focused on investigating how pruning impacts NN generalization [39, 40, 41]. However, prior studies have primarily concentrated on either unit pruning or edge pruning in isolation, without employing both in a sequential manner as proposed in our work. In our approach. we employ unit pruning as a means to condition or compel NNs to learn reused sub-functions effectively. Furthermore, edge pruning is employed to uncover the sparse connectivity between various units or modules.
Mechanistic interpretability seeks to reverse-engineer trained NNs to understand their internal mechanisms. One avenue of research within mechanistic interpretability involves identifying the circuits formed within NNs. Recent discoveries include curve-detecting circuits in vision models [42, 43], transformer circuits [44], induction heads [45], and indirect object identification [46], among others. Our proposed approach for uncovering the hierarchical modular task structure dissects the NN into modules responsible for learning specific sub-functions. Hence, simplifying the complexity of reverse engineering entire NNs, by focusing instead on smaller sub-networks.
Continual learning aims learning multiple tasks presented sequentially while preserving perfor- mance on previously learned tasks [47, 48, 49, 50J. Modular NNs have been demonstrated to mitigate catastrophic forgetting by freezing and reusing certain modules while introducing and updating others to learn new tasks [6, 7, 8]. However, those methods entail manually designing modular NNs with fixed module sizes at initialization. NNs that naturally acquire hierarchically modular structure mirroring that of the task may offer additional advantages compared to generic modular NNs. These potential benefits encompass enhanced generalization, efficient transfer learning through the reuse of modules corresponding to frequently utilized sub-functions, and informed module additions to prevent sub-linear increases in NN capacity.
7 Conclusion
We have introduced Neural Sculpting, a methodology to uncover the hierarchical and modular structure of target tasks in NNs. Our findings first demonstrated that NNs trained conventionally do not naturally acquire the desired structural properties related to input separable and reused sub- functions. To address this limitation, we proposed a training strategy based on iterative pruning of units and edges, resulting in sparse NNs with those previous structural properties. Building upon this, we introduced an unsupervised method to detect modules corresponding to various cob-functions while also uncovering their hierarchical organization. Finally, we validated our proposed methodology by using it to uncover the underlying structure of a diverse set of modular and hierarchical tasks.
As future research direction, we could investigate the efficiency and theoretical underpinnings of modularity in function graphs, which could further motivate pruning NNs. One potential approach to overcome the computational costs and dependence on initial architecture depth could be to use neural architecture search algorithms to construct modular NNs during training. Additionally, exploring the use of attention mechanisms and transformers to uncover hierarchical modularity in tasks could be an interesting direction for future work. These approaches could provide more efficient way of obtaining modular NNs that can also better capture the underlying structure of the target task.
10

---

Acknowledgements
This work is supported by the National Science Foundation (Award: 2039741), by the EU's Horizon 2020 Research and Innovation Program (grant agreement no. 739578), and by the Government of the Republic of Cyprus through the Deputy Ministry of Research, Innovation, and Digital Policy. The authors acknowledge the constructive comments given by the NeurlPS 2023 reviewers, Cameron Taylor, Qihang Yao and Mustafa Burak Gurbuz.
References
[1] Herbert A Simon. The architecture of complexity. In Facets of systems science, pages 457-476. Springer, 1991.
[2] Günter P Wagner, Mihaela Pavlicev, and James M Cheverud. The road to modularity, Nature Reviews Genetics, 8(12):921-931, 2007.
[3] David Meunier, Renaud Lambiotte, Alex Fornito, Karen Ersche, and Edward Bullmore. Hierarchical modularity in human brain functional networks. Frontiers in neuroinformatics, 3:37, 2009.
[4] Miguel Valencia, MA Pastor, MA Fernández-Seant J Artieda, Martinerie, and M Chavez. Complex modular structure large-scale brain networks. Chaos: An Interdisciplinary Journal of Nonlinear Science, 19(2):023119 2009.
[5] David Meunier, Renaud Lambiotte, and Edward T Bullmore. Modular and hierarchically modular organization of brain networks. Frontiers in neuroscience, 4:200, 2010.
[6] Tom Veniat, Ludovic Denoyer, and Marc' Aurelio Ranzato. Efficient continual learning with modular networks and task-driven priors. arXiv preprint urXiv:20/2.2663/ 2020.
[7] Jorge A Mendez and Eric Eaton. Lifelong learning of compositional structures. arXiv preprint arXiv:2007.07332, 2020.
[8] Oleksiy Ostapenko, Pau Rodriguez, Massimo Caccia, and Laurent Charlin. Continual learning via local module composition. Advances in Neural Information Processing Systems, 34:30298- 30312, 2021.
[9] Dzmitry Bahdanau, Shikhar Murty, Michael Noukhovitch, Thien Huu Nguyen, Harm de Vries, and Aaron Courville. Systematic generalization: what is required and can be learned? arXiv preprint arXiv: 1811. 12889, 2018.
[10] Brenden Lake and Marco Baroni. Generalization without systematicity: On the compositional skills of seguence-t--sequenee recurrent networks. In International conference on machine learning, pages 2873-2882. PMLR, 2018
[11] Dieuwke Hupkes, Verna Dankers, Mathijs Mul, and Elia Brumi. Compositionality decomposed: how do neural networks generalise? Journal of Artificial Intelligence Research, 67:757-795, 2020.
[12] Chihiro Watanabe, Kaoru Hiramatsu, and Kunio Kashino. Modular representation of layered neural networks. Neural Networks, 97:62-73, 2018.
[13] Chihiro Watanabe. Interpreting layered neural networks via hierarchical modular representation. In International Conference on Neural Information Processing, pages 376-388. Springer, 2019.
[14] Daniel Filan, Stephen Casper, Shlomi Hod, Cody Wild, Andrew Critch, and Stuart Russell. Clusterability in neural networks. arXiv preprint arXiv:2103.033350 2021.
[15] Shlomi Hod, Stephen Casper, Daniel Filan, Cody Wild, Andrew Critch, and Stuart Russell, Detecting modularity in deep neural networks. arXiv preprint 1XXi:2110000058. 2021.
[16] Richard I Lange, David S Rolnick, and Konrad Kording. Clustering units in neural networks: upstream downstream information, arXiv preprint 2103
11

---

[17] Róbert Csordás, Sjoerd van Steenkiste, and Jürgen Schmidhuber. Are neural nets modu- lar? inspecting functional modularity through differentiable weight masks. arXiv preprint arXiv:2010.02006, 2020.
[18] Jeff Clune, Jean-Baptiste Mouret, and Hod Lipson. The evolutionary origins of modularity. Proceedings of the Royal Society b: Biological sciences, 280( (55):201 2013.
[19] Henok Mengistu, Joost Huizinga, Jean-Baptiste Mouret, and Jeff Clune. The evolutionary origins of hierarchy. PLoS computational biology, 226))e100488)) 2016.
[20] R Ryan Williams. Limits representing boolean functions by linear combinations of simple functions: Thresholds, relus, and low-degree polynomials. arXiv preprint 2018.
[21] Song Han, Jeff Pool, John Tran, and William Dally. Learning both weights and connections for efficient neural network. In Advances in neural information processing systems, pages 1 1135- 115--113,, 2015.
[22] Steven A Janowsky. Pruning versus clipping in neural networks. Physical Review A, (9(1))66600, 1989.
[23] Sejun Park*, Jacho Lee", Sangwoo Mo, and Jinwoo Shin. Lookahead: A far-sighted alternative of magnitude-based pruning. In International Conference on Learning Representations, 2020.
[24] Yann LeCun, John S Denker, and Sara A Solla. Optimal brain damage. In Advances in neural information processing systems, pages 598-605, 1990.
[25] Leslie N Smith. Cyclical learning rates for training neural networks. In 2017 IEEE winter conference on applications of computer vision (WACV), pages 464 464-472. IEEE, 2017.
[26] Alex Renda, Jonathan Frankle, and Michael Carbin. Comparing rewinding and fine-tuning in neural network pruning. arXiv preprint arXiv:2003.0233: 02388, 2020.
[27] Xiaoqin Zeng and Daniel S Yeung. Hidden neuron pruning of multilayer perceptrons using quantified sensitivity measure. Neurocomputing, 69(7-9):825-337, 2006.
[28] DANIEL Yeung and Xiao-Qin Zeng. Hidden neuron pruning for multilayer perceptrons using sensitivity measure. In Proceedings. International Conference Machine Learning and Cybernetics, volume 4, pages 1751-1751 IEEE, 2002.
[29] Bo Li and Cheng Chen. First-order sensitivity analysis for hidden neuron selection in layer-wise training of networks. Neural Processing Letters, 48: 105- 1121, 2018.
[30] Namhoon Lee, Thalaiyasingam Ajanthan, and Philip Torr. SNIP: SINGLE-SHOT NETWORK PRUNING BASED ON CONNECTION SENSITIVITY. In International Conference on Learning Representations, 2019.
[31] Michelle Girvan and Mark EJ Newman. Community structure in social and biological networks. Proceedings of the national academy of sciences, 99(12))7821-7826 2002.
[32] Mark EJ Newman and Michelle Girvan. Finding and evaluating community structure in networks. Physical review E, 69(2):026113, 2004.
[33] Mark EJ Newman. Modularity and community structure in networks. Proceedings of the national academy of sciences. 103(23):8577-852 2006.
[34] Suraj Srinivas and R Venkatesh Babu. Data-free parameter pruning for deep neural networks. arXiv preprint 150.0061070 2015.
[35] Hengyuan Hu, Rui Peng. Yu- Yu-Wing Tai, and Chi-Keung Tang. Network trimming: A data-driven neuron pruning approach towards efficient deep architectures. arXiv preprint arXiv: 2016.
[36] Chaoqi Wang, Guodong Zhang, and Roger Grosse. Picking winning tickets before training by preserving gradient flow. In International Conference on Learning Representations, 2019.
12

---

[37] Hidenori Tanaka, Daniel Kunin, Daniel L Yamins, and Surya Ganguli. Pruning neural networks without any data by iteratively conserving synaptic flow. Advances in Neural Information Processing Systems, 33, 2020.
[38] Shreyas Malakarjun Patil and Constantine Dovrolis. Phew: Constructing sparse networks that learn fast and generalize well without training data. In International Conference on Machine Learning, pages 8432-8442. PMLR, 2021.
[39] Siddhaling Urolagin, Prema KV, and NV Subba Reddy. Generalization capability of artificial neural network incorporated with pruning method. In Advanced Computing, Networking and Security: International Conference, ADCONS 2011, Surathkal, India, December 16-18, 2011, Revised Selected Pupers, pages 171-178. Springer, 2012.
[40] Brian Bartoldson, Ari Morcos, Adrian Barbu, and Gordon Erlebacher. The generalization- stability tradeoff' in neural network pruning. Advances in Neural Information Processing Systems, 33:20852-20864, 2020.
[41] Tian Jin, Michael Carbin, Daniel M Roy, Jonathan Frankle, and Gintare Karolina Dziugaite. Pruming's ' effect on generalization through the lens of training and regularization. arXiv preprint 1xXiv:2210.137366 2022.
[42] Chris Olah, Nick Cammarata, Ludwig Schubert, Gabriel Goh, Michael Petrov, and Shan Carter. Zoom in: An introduction to circuits. Distill, 5(3):c00024-000 001, 2020.
[43] Nick Cammarata, Gabriel Goh, Shan Carter, Ludwig Schubert, Michael Petrov, and Chris Olah. Curve detectors. Distill, 2020. https://distill. http://hhlllllll22///////uuu//ee
[44] Nelson Elhage, Neel Nanda, Catherine Olsson, Tom Henighan, Nicholas Joseph, Ben Mann, Amanda Askell, Yuntao Bai, Anna Chen, Tom Conerly, Nova DasSarma, Dawn Drain, Deep Ganguli, Zac Hatfield-Dodds. Danny Hernandez, Andy Jones, Jackson Kernion, Liane Lovitt, Kamal Ndousse, Dario Amodei, Tom Brown, Jack Clark, Jared Kaplan, Sam McCandlish, and Chris Olah. A mathematical framework for transformer circuits. Transformer Circuits Thread, 2021. http::/ttansfoomee--cciiitt http://cic....poo/////////eee/nn /wtp////wwo///deeee..mm//m
[45] Catherine Olsson, Nelson Elhage, Neel Nanda, Nicholas Joseph, Nova DasSarma, Tom Henighan, Ben Mann, Amanda Askell, Yuntao Bai, Anna Chen, et al. In-context learning and induction heads. arXiv preprint arXiv:2209.1 18895, 2022.
[46] Kevin Wang, Alexandre Variengien, Arthur Conmy, Buck Shlegeris, and Jacob Steinhardt. Interpretability in the wild: a circuit for indirect object identification in gpt-2 small. URL https://arxiv. org/abs/2211.005000 2022.
[47] Andrei Rusu. Neil C Rabinowitz, Guillaume Desjardins. Hubert Soyer, James Kirkpatrick, Koray Kavukcuoglu, Razvan Pascanu, and Raia Hadsell. Progressive neural networks. arXiv preprint arXiv: 1606. 04671, 2016
[48] Zhizhong Li and Derek Hoiem. Learning without forgetting. IEEE transactions on pattern analysis and machine intelligence, (0(12):2935-9944 2017.
[49] James Kirkpatrick, Razvan Pascanu, Neil Rabinowitz, Joel Veness, Guillaume Desjardins, Andrei A Rusu, Kieran Milan, John Quan, Tiago Ramalho, Agnieszka Overcoming catastrophic forgetting in neural networks. Proceedings of the national academy of sciences, 1 114(13):351-3352,, 2017.
et al.
[50] Friedemann Zenke, Ben Poole, and Surya Ganguli. Continual learning through synaptic intelligence. In International Conference on Machine Learning, pages 3987-3995. PMLR, 2017.
[51] Fengxiang He, Tongliang Liu, and Dacheng Tao. Control batch size and learning rate to generalize well: Theoretical and empirical evidence. Advances in Neural Information Processing Systems, 32, 2019.
[52] Simran Kaur, Jeremy Cohen, and Zachary Chase Lipton. On the maximum hessian eigenvalue and generalization. In Proceedings on, pages 51-65. PMLR, 2023,
13

---

[53] Yuanzhi Li, Colin Wei, and Tengyu Ma. Towards explaining the regularization effect of initial large learning rate training neural networks. Advances in Neural Information Processing Systems, 32, 2019.
[54] Stanislav Fort, Pawel Krzysztof Nowak, Stanislaw Jastrzebski, and Srini Narayanan. Stiffness: new perspective on generalization in neural networks. arXiv preprint arXiv: 190100999, 2019.
[55] Peter Rousseeuw. Silhouettes: graphical aid the interpretation and validation of cluster analysis. Journal of computational and applied mathematics, 20:53-65, 1987.
[56] Tadeusz Caliński and Jerzy Harabasz. A dendrite method for cluster analysis. Communications in Statistics-theory and Methods, 3(1):1-27, 1974.
[57] David I. Davies and Donald W Bouldin. A cluster separation measure. IEEE transactions on pattern analysis and machine intelligence, (2):2244227, 1979.
14

---

A Appendix structure and details
In this section, we discuss the structure of the appendix. The code and datasets used can be found here: https://git thub. htt.uu...o///ayyaaaaaaaaaaaaaa
Appendix sections (B F) accompany section 5 in the main paper and provide visualizations of neural networks (NNs) and the hierarchical modularity uncovered by our proposed pipeline. Each section includes NN visualizations corresponding the five experiments summarized in the main paper. The main figures in these sections are organized such that the first row represents different function graphs that the NNs are trained to learn, with each column representing a distinct function graph relevant to the experiment. The subsequent rows show visualizations of the uncovered hierarchical modular structures for NNs with increasing depths.
Visualization figure details: In the appendix sections, each function graph is associated with visualizations from specific NN trial at partieular depth value (with one width value and one seed value). This visualization represents the structure that is commonly recovered for the given function graph and NN depth. While the NN width value and seed value remain consistent in the visualizations, they may vary if the recovered structure does not represent the majority. We also present and discuss other structures that are frequently recovered, using other function graphs representing the same Boolean function. For success rate computations, such trials are typically considered failures in recovering overall structures. However, for individual sub-function detection success rates, they may be considered successful if they uncover a module corresponding to that sub-function. Additional visualizations and the hyperparameters used for training and pruning the NNs are detailed in the code base
Function graph nomenclature: In the visualizations, the term "modularity" indicates the function graph being used. The modularity is represented as a list that indicates the number of sub-functions in the hierarchy. For example, if the modularity is [1, 2], it means there upper hierarchical level that take as input the output of a single sub-function lower in the hierarchy. In the code base, we prepend the number of input nodes and append the number of output nodes to this list.
sub-functions in the
Appendix section G accompanies section 2 in the main paper. Section 2 presents two tests developed to demonstrate that NNs, through standard training, do not acquire structural properties reflecting input separable and reused sub-functions In appendix section G, we provide detailed results for these tests conducted on nine different NN architectures to further support our claims. We also report the results of the same tests conducted edge- pinge-prunedd and unit-edge-prumntt NNs.
Appendix section H accompanies section 3 in the main paper, which presents the method for pruning NNs. This appendix section provides detailed explanation of the unit and edge pruning algorithms, along with the exploration strategy and results for hyperparameter tuning.
Appendix section accompanies section 4 in the main paper, which introduces the proposed method for detecting modules corresponding various sub-functions. In this appendix section, we present detailed algorithm description and the methodology used for hyperparameter exploration.
Note that the pruning and module detection hyperparameters were explored concurrently. However, in the appendix section, we first present experiments with the pruning hyperparameters while keeping the module detection method fixed, and vice versa.
Resources: The unit and edge pruning processes for the Boolean functions were executed on a CPU, while the pruning for the MNIST experiment was performed using RTX6000 GPUs.
15

---

B NN visualizations: Function graphs used for validation
Input separahle sub-function
Reused function
Input separable reused
Single sub-function
wwk.brbyll woile
arnd-1
A -222
K.ito x12
Autt ad
Peddietgl Demiyy
nes aesdarrdd Z.Aet a. unitly Lans
MECHER ONIT
MaCEMNOO wattl UMARY LAbe
6-500
Figure The visualizations provide examples of NNs successfully uncovering the exact hierarchical structure the validation function graphs. Each column represents distinct function graph, characterized by: input separable sub-functions, 2. reused sub-function, input separable and reused sub-functions, or 4. single sub-function Each row showcases NNs with different depths: 1. one hidden layer, two hidden layers, and 3. three hidden layers.
16

---

C NN visualizations: Function graphs with a single sub-function and increasing reuse
Figure 15: The function graphs consist of single non-input separable sub-function that is reused to construct two oulput sub-functions. We vary the number of times the two sub-functions are used or replicated, ranging from to 8.
990999
ROOPER
Figure 16: Function graphs in Figure 15 represented using only 3 hierarchical levels.
modderatt weik mocoeeettt
Bata JRAMEU Dandy
Hhis way SLANEE Seda
Auddeng AMRA IN LIN.
Figure 17: Example visualizations of uncovered modular and hierarchical structure for NNs trained on function graphs in Figure 15. Each row indicates different NN depth, 1. hidden layer, 2. 2 hidden layers, and 3. hidden layers. Each column indicates a different function graph with sub-function use increasing from to 8. We can observe that when the NN depth is lower than that of the number of hierarchical levels, a single module is recovered. This is consistent with the function graphs that only 3 hierarchical levels shown in Figure 16.
17

---

D NN visualizations Increasing input overlap and reuse of two input separable sub-functions
D.1 Completely separable sub-functions
NoieetyDiAA 24
1-908-122
AH61A-0
Figure 18: The visualizations presented illustrate the uncovered modular and hierarchical structure of NNs trained on the function graphs depicted the first row. Within these function graphs, there two sub-functions that entirely input separable. Each in the visualizations corresponds to different NN depth, namely hidden layer, hidden layers, and 3 hidden layers. Additionally, each column represents different function graph, where the usage of sub-function increases incrementally from to 8.
18

---

D.2 Single overlapping input node
Awngy
Figure 19: The visualizations provided showcase the uncovered modular and hicrarchical structure of NNs trained function graphs found in the first row. These function graphs comprise two sub-functions that are built using three sets of input nodes. Specifically, there are two sets, each containing three nodes, which are specific to individual sub-functions. The third set consists of one input node that is shared between both sub-functions. In the visualizations, each row corresponds to different NN depth, ranging from hidden layer hidden layers. Additionally, each column represents a distinct function graph, with an increasing usage of sub-functions from to 8.
19

---

D.3 Two overlapping input nodes
NOW
SLAAN PL2E
Figure 20: The provided visualizations depict the uncovered modular and hicrarchical structure of NNs trained function graphs found in the first row. These function graphs comprise two sub-functions that are constructed using three sets of imput nodes. Within these sets, there are two cubb-function-spccine sets, each consisting of two nodes, and the third set comprises shared between both sub-functions. the visualizations, each row represents a different NN depth, ranging from hidden layer to hidden layers. Furthermore, each column represents distinct function graph, with increasing usage of fub-functions from to
input nodes
20

---

D.4 Three overlapping input nodes
modderge wnth
MANZA JAWE LL SLATT
Mad merr ANDL SHET
2013
Nobde BLAND 2E31
theart
Figure 21: The provided visualizations showcase the most commonly uncovered modular and hierarchical structure for NNs trained on function graphs found in the first row. These function graphs consist two sub-functions that are constructed using three sets of input nodes. Among these sets, two cub-function-speele of three input nodes that are shared between both functions.. Each row in the visualizations represents different NN depth, ranging from hidden layer to 3 hidden layers. Additionally, each column corresponds to a distinct function graph, with an increasing usage of sub-functions from 1 to 8. Observing the visualizations, we can note that the input units accurately clustered into two modules specific to each sub-function and one reused module. However, the hidden units in the early layers tend to be clustered into single module more often. This suggests that NNs may learn intermediate states that are reused for both sub-functions when there is large input reuse set. This phenomenon may be influenced by excessive hidden unit pruning and the existence of learnable hidden states that can be reused independently of input reuse. On the other hand, the output sub-function are detected accurately for deeper NNs, indicating that the hierarchical organization better captured as the network depth increases.
with each set comprising
node, while the third consists
NOOOWNREA JLACE, AAI DENEGY
Figure 22: The provided visualizations depict accurately uncovered modular and hierarchical struc- tures for NNs trained on function graphs shown in Figure 21.
21

---

The visualizations highlight the tendency of NNs trained function graphs from Figure 21 to cluster the input and early hidden layers together while accurately detecting the output sub- functions. This clustering of the input layer and early hidden layers into single module suggests that the NNs learn representations that are shared among the sub-functions, despite their distinct inputs. This phenomenon becomes more pronounced when the sub-functions are repeatedly utilized within the function graph. It is possible that the network captures common features or patterns that relevant all the sub-functions, leading to this shared module in the early layers.
Figure 23:
D.5 All overlapping input nodes
IAMO.
10000217 BAM SLOWN,
BELLE
Figure 24: In the set of visualizations for the uncovered modular and hierarchical structure of NNs trained on function graphs in the first row, we can observe single module being recovered. This finding is consistent with the previous result, where high degree of input overlap within the function graph, coupled with hidden unit pruning, influences the NN to learn hidden states that are reused for both output sub-functions. Despite the presence of distinct output sub-functions, the network learns to capture common underlying features in all the hidden layers.
22

---

Figure 25: In set 2 of visualizations for the uncovered modular and hierarchical structure of NNs trained function graphs in the first row, distinct pattern emerges. In the early layers, the pipeline consistently recovers a single module, primarily because there is no input separability present in the function graphs. However, as we progress the later layers, observe successful separation of units into two distinct modules.
Podde
A-HECL-0
Figure 26: In set 3 of visualizations for the uncovered modular and hierarchical structure of NNs trained on function graphs in the first row, intriguing patterns emerge. The pipeline successfully reveals a single module in the input layer. In later layers, the units are accurately separated into two distinct modules. In NNs with hidden layers, we observe that the first hidden layer has two distinct clusters. One cluster is connected to one of the output modules, while the other cluster is reused by both modules. In NNs with hidden layers, The first hidden layer approximates two funcctunssons, which are subsequently reused by both output modules through an intermediate module. We could not interpret those structures using any of the valid function graphs.
23

---

E
NN visualizations Increasing the number of hierarchical levels
2999
Noca
-.....A.... -1.
A.d U.A.A...
1--00---111 -13
Deraly
Mod Aurbat Ardi es de
sealengt Aorts 45 48 10E Deanity
PadS WEME 23 18-45 Derdte--da 122%%
Pacderayla 2tase da as Du
Aeni ALLE Deni wode
Figure 27: The visualizations of the uncovered modular and hierarchical structure for NNs trained on function graphs in the first row provide valuable insights. Within these function graphs, there two sub-functions that completely input separable. The outputs of these sub-functions then combined into single sub-fum fobeffnctiin,, which is subsequently reused by two output sab-funciions. Each row the visualizations corresponds to different NN depth, ranging from hidden layer hidden layers. Additionally, each column represents a different function graph, with increasing number of sub-function uses ranging from to 8. interesting observation that as the depth of the NN varies, the uncovered hierarchical structures also vary. These visualizations shed light on the interplay between network depth and the discovered hierarchical structures, offering insights into how the NNs adapt and represent the relationships among the input separable sub-functin functions and the output sub-fume functions.
24

---

E.1 Other structures frequently recovered
Mekierdhh 2.23 Auig
SESTH IND
Figure 28: The visualizations showcase other structures that are frequently uncovered by NNs trained on the function graph in the first is evident that the function also be represented by other function graphs shown in the same row. However, these alternate function graphs are less efficient in terms of the number of edges and gate nodes required. In the first alternate graph, observe the use of 6 additional edges, while the second alternate graph utilizes additional edges. Moreover, both of these function graphs involve larger number of gate nodes compared to the original function graph. Many unsuccessful NN trials result in the recovery of these alternate structures, as illustrated in the second row of the visualizations.
Podderat 1.21 ACEL do CLOMANY 3/25
Figure 29: The visualizations showcase other structures that frequently uncovered by NNs trained on the function graph in the first row. is evident that the function can also be represented by other function graphs shown in the same row. However, this altemnte function graph is less efficient, requiring 2 additional edges compared to the original function graph. Many unsuccessful NN trials result in the recovery of these alternate structures, illustrated in the second row of the visualizations.
25

---

E.2 Output sub-functions used once
Figure 30: Function graphs representing the Boolean function in 27 when each of the output sub- functions is used only once. In each of the figure, numbers of hierarchical levels. Each graph within a row presents an alternate representation of the function, employing the same number of nodes and edges.
observe function graphs with different
shuelt 16.31 C4
Figure 31: a) Example visualization of the hierarchical structure obtained through an NN with hidden layers, trained on the function illustrated in Figure 30(same structure as shown Figure 30, row 3a); b) Example visualization of the hierarchical structure obtained through an NN with 3 hidden layers, trained on the function illustrated in Figure 30 (same structure as shown in Figure 30, row 2a): c) Example visualization of the hierarchical structure obtained through an NN with 3 hidden layers, trained on the function illustrated in Figure 30 (same structure as shown in Figure 30, row 2b); d) Example visualization of the hierarchical structure obtained through an NN with 4 hidden layers, trained on the function illustrated Figure 30 (same structure as shown in Figure 30, row la); Example visualization of the hierarchical structure obtained through an NN with 4 hidden layers, trained on the function illustrated Figure 30 (same structure as shown in Figure 30, row Ic).
26

---

NN visualizations for tasks with MNIST
F1
MNIST task classifying two digits
Modularity[I2: A5e,, 784, 784, 20]: Density 0.12%
(n 0.001, batch size =112, epochs -40, seed -0, arth -(836, 26, 25, 20) =30.0.
ModularityIz]: Arch[136B, 784, 7B4, 784, 20]: Density 0.68%
epocto 10,
P. 13000000 =1.0
Modularityf21: Arch(1568. 784, 784, 784, 784, 201: Density 0 0.07%
N- 0.001, batch -256, spacts -10, seed -0, arch -1801 23, 20, 16, 20]
P. -20.0,022 =0.
Figure 32: Visualizations NNs uncovering two modules corresponding to the two MNIST digits classification task with varying depth. Out of the 36 trials conducted, we obtain two completely separable modules for 33 out of 36 trials, indicating the high effectiveness of our approach.
27

---

F22
Hierarchical task with MNIST digits
Modularity(2, 3]: Arch[1580, 784, 784, 3): Density 0.15%
Modularity12, Arch[1568, 784. Density 0.12%
0,001, batch sice 512, epochs 80, seed -0, arch (026, 72, 12, My m200 295
0.001 batch =256, epochs -10 seed =0. arch ((326, 61, 17.
P. -10.0, P. =1.0
Modidderity(,. Ap Arch(1 964, 784, 784, 788, 784, 5): Deinvity 0.07%
Modilarity?? *] Arche 1588, 7850, 784, 784, 784, %] Density = 05%.
spochs
Figure 33: The uncovered NN structures for the hierarchical and modular task with 2 MNIST digit images input. The NNs uncover the three output modules accurately. The pipeline fails to recover the two input separable modules when the NN depth is low. Deeper NNs do recover two input separable modules. However, the middle layers are clustered into a single module indicating that the depth may be insufficient to detect the two classification modules accurately.
28

---

G Structural properties of dense and sparse NNs
T-statistic for with varying width and depth, Test
T-statistic values for dense NNs with varying width and depth, Test 2
-19.43
1.38
-1.77
88.00
25
wilth
.20.31
5.62
3.91
with
-11.79
-1.78
-25
-30
-15
-9.11
-2.35
0.44
-15
-13.50
5.15
-0.00
-20
-22
layers
layers
values for dense MNs with varying width and depth, Test
values for dense NNs with varying width and depth, Test
-10
0.00
0.91
0.06
-00
0.00
0.00
0.96
-00
wdtt
0.00
1.00
1.00
wdth
0.00
0.00
0.06
-04
-44
0.00
0.03
0.66
+2
0.00
1.00
0.27
-2
hiddon layers
hiddon layers
Figure 34: T-statistic and P-values for the two statistical conducted detect input separability in dense NNs. The first row shows the heat maps of I-statistic values (on the two tests) for NNs with varying widths and depths. The second row shows the p- p-values for the same.
T-statistic values for edge pruned NNs with varying width and depth, Test
T-statistic values for edge pruned NNs with varying width and depth, Test
X
200
39.83
-50
330
widh
200
-242.41
-834.46
-27.27
-171.41
-31.55
-20.05
125
-000
-150
-189.24
-39.83
-73.86
700
+89
25
-105.14
-213.80
200
hidden layers
hidden layers
values for pruned with width and depth, Test
values for pruned with width and depth, Test
0.00
0.00
0.00
0.00
0.00
0.000
0.500
0025
widh
0.00
0.00
0.00
0.00
00090
0.00
0.00
0.00
875
0.00
0.00
0.00
008
-0300
0.300
hidden
hidden
Figure 35: T-statistic and P-values for the two statistical tests conducted to detect input separability in edge-pruned NNs. The first shows the heat maps of t-statistic values (on the tests) for NNs with varying widths and depths. The second row shows the p-values for the same.
29

---

Tsstaistic values for unit-edge pruned NNs with verying and depth,
T-statistic values for unit-edge pruned NNs with varying width and depth, Test
-180.74
56.39
-35.07
X
-123.24
-78.00
-40.80
400
width
-29.97
-300
-75,70
65.75
-156.11
-1000
663.88
-32.22
-49.98
hidden layers
hidden layers
values for unit-edge pruned NNs with verying width and depth, Tlss
values for unit-edge prumed NNs with verying width and depth, Tlest
0.50
0050
0005
0005
widti
0.00
0.00
0.00
0.000
0.00
0.00
0.00
0.00
0.00
0.00
0.00
-0 878
00095
-0 388
-0
hidden layers
hidden layers
Figure 36: T-statistic and P-values for the two statistical tests conducted to detect input separability in unit and edge pruned NNs. The first row shows the heat maps of t-statistic values (on the two tests) for NNs with varying widths and depths. The second row shows the p-values for the same.
H Pruning Algorithms
This appendix section is a companion to section the main paper. Here, we provide detailed explanation of the pruning algorithm and outline the experiments conducted to explore hyper- parameters for training and pruning NNs.
H.1 Details
The pseudo code for the unit pruning algorithm can found in Algorithm 1, while the pseudo code for the edge pruning algorithm is provided in Algorithm 2. In each iteration, pruning is performed (either units or edges), followed by training the NN for the same number of epochs and using the same learning rate schedule.
The pruning procedure consists of two steps. First, score is assigned to each unit/edge, and then fraction of the units/edges is pruned based on these scores. It is important to note that the pruning fractions (Pu. Pe. and p) always computed relative the original number of hidden units or edges in the NN.
Both unit pruning and edge pruning implemented using binary masks. Each edge weight is assigned a binary mask value, where a value indicates that the edge weight is not prumed, and a value of 0 indicates that it is pruned. When unit is pruned, all incoming and outgoing edge weights associated with that unit are masked out by setting their binary mask values to O.
Unit and edge pruning gradients: In our experiments, we conducted grid search over the Pu and values for each NN architecture, function graph, and seed value. We explored range of 14 different Pu values, ranging from 5% 70% in increments of 5%, and different Pe values: 0.5. 1.0, 1.5, 2.0, 2.5. It is important to note that the Pa values used throughout the process are relative to the original number units in the NN, while the P. values are relative to the number of edges in the original NN. After the grid search, we select the NN with the lowest density among all the sparse NNs obtained. Typically, we find that higher unit pruning gradients (p.. > 40) work best, as they allow for the removal of a lower number of units in each iteration by halving the gradient value.
30

---

Algorithm 1: Unit pruning algorithm
Data: 0 E RR, (2,, (,)),,, (2, V.), Pu. scoring metric, [.(0, (N ).) (loss sensitivity)
Result: mask, M
+ train 0, (X v:))
/* Train the dense NN */
A. f- Acc 0, X v1 vo));
p 1 0;
/* Assign initial pruning percentage as 0 */
Pmin 100/ Ni):
/* minimum pruning percentage difference */
prume + True;
while prune True do
p p P.PPu:
- f.(0. (x v.))
/* Pruning scores equal to loss sensitivity */
T < percentile( (S,
M, - I):
/* Threshold the scores to obtain mask */
O, + 1 0pM
O, + train(O,: v.))))
/* Train the NN */
A < acc(0p. (X y )))
A >= A, then
0 pp:
else
p p pui
Pu +- Pa /2;
if Pu Pmin then prune t False;
end
end
end
Algorithm 2: Edge pruning algorithm
Data: 0 E R2, (X,, V.), (K,, V.), Pe Result: mask, M
+ train( 0, (X V.));
/* Train the dense NN */
A +- Acc 0, (X v. )o));
+ 0;
/* Assign initial pruning percentage as 0 */
Pmin 100/a:
/* minimum pruning percentage difference */
prune + True;
while prune == True do
p p pei
- 00
/* Pruning scores equal to the weight magnitude */
T < Percentile(S.pl,
M, + I(S>1 T);
/* Threshold the scores to obtain mask
0, + 0 OOM;
Mp;
6, + train (x,,).)
/* Train the NN */
A < Acc p. (X y W)));
> A, then
0 < Op
else
p p Pei
Pe +- 2:/
if < Dmin then prune t False;
end
end
end
31

---

Ingut segantble
sub--function
Ispui separable and reseed
Single
00000909
cooceoop
Negation
Figure 37: Function graphs used to validate the proposed pipeline
Table 2: Success rates for NNs with varying learning rate and batch size, used for training on function graph with a. imput separable sub-functions, and b. reused sub-function.
Input separable fub-functions
Reused fun-tunction
0.005
0.01
0.05
Ir
0.005
0.01
0.05
0.1
batch size
batch size
Reused
NNs with
Hidden Layer
NNs with 1 Hidden Layer
1.0
1.0
0.5
0.5
1.0
1.0
1.0
1.0
1.0
1.0
2
0.5
0.5
1.0
1.0
4
1.0
1.0
1.0
1.0
0.5
1.0
1.0
1.0
8
1.0
1.0
1.0
1.0
8
X
0.5
0.75
1.0
16
X
1.0
1.0
1.0
16
x
1.0
1.0
NNs with 2 Hidden Layers
NNs with 2 Hidden Layers
1.0
1.0
1.0
X
0.25
0.25
0.5
X
1.0
1.0
1.0
2
0.5
0.0
0.75
1.0
4
1.0
1.0
1.0
1.0
0.25
1.0
8
1.0
1.0
1.0
1.0
8
0.25
0.0
0.5
1.0
1.0
1.0
1.0
1.0
16
0,25
0.75
0.5
NNs with 3 Hidden Layers
NNs with 3 Hidden Layers
1.0
1.0
X
x
0.25
0.5
X
2
1.0
1.0
X
x
2
0.25
0.5
X
1.0
1.0
1.0
0.5
0.5
0.75
X
1.0
1.0
1.0
0.25
0.25
0.75
1.0
16
1.0
1.0
1.0
1.0
16
X
0.75
1.0
H.2 Learning rate and batch size experiments
In this section, we conduct experiments to investigate the impact of learning rates and batch sizes on the structures obtained through pruning. Previous studies have examined the roles of these hyper-parametert in terms of convergence, generalization, and the ability of NNs to find global optima [51, 52]. However, most of these studies train NNs for fixed number of epochs iterations, which may not be suitable for our experiment as we require the original dense NNs to learn the task effectively.
To determine the appropriate number of epochs, we aim for the NNs with the four considered seed values to achieve 100% validation accuracy. We set maximum of 120 epochs to avoid excessively long training or pruning times. Consequently, some combinations of learning rates and batch sizes do not achieve 100% validation accuracy. These combinations typically fall into two categories: I) high learning rates and low batch sizes leading to unstable training, and 2) low learning rates and high batch sizes resulting in insufficient number of training iterations to achieve 100% validation accuracy. Such cases are marked with an Xin the result tables.
We validate and tune hyperparameters for our pipeline using four function graphs shown in Figure 37. These graphs include input separable sub-functions, reused sub-functions, a combination input separable and reused sub-functions, and non-modular function graph. We then train and prune NNs with width 24 and varying depths, reporting the success rates for detecting the same hierarchical structure the function graph.
32

---

Table 3: Success rates for NNs with varying learning rate and batch size, used for training on function graph with a. input separable and reused sub- functions, and b. a single sub-function non-modular graph).
Ir
0.005
0.01
0.05
0.1
batch size
NNs with
Hidden Layer
0.75
1.0
1.0
X
0.005
0.01
0.05
0.1
0.75
0.75
1.0
1.0
batch size
Single
0.75
0.5
1.0
1.0
1.0
1.0
1.0
1.0
0.5
0.75
1.0
1.0
1.0
1.0
1.0
1.0
0.75
1.0
1.0
1.0
1.0
1.0
1.0
1.0
32
0.75
1.0
1.0
1.0
1.0
1.0
1.0
64
X
0.75
1.0
1.0
16
X
X
1.0
1.0
NNs with 2 Hidden Layers
NNs with 2 Hidden Layers
0.75
1.0
0.25
1.0
1.0
1.0
1.0
0.25
X
0.75
0.75
1.0
1.0
0.75
1.0
0.0
x
1.0
0.75
1.0
1.0
1.0
1.0
1.0
0.75
1.0
1.0
1.0
16
1.0
1.0
1.0
0.25
16
1.0
1.0
1.0
1.0
1.0
1.0
1.0
0.5
NNs with Hidden Layers
64
1.0
0.75
1.0
1.0
0.25
1.0
1.0
X
NNs with 3 Hidden Layers
0.5
0.75
0.5
X
1.0
1.0
x
x
0.75
1.0
1.0
X
0.75
1.0
X
1.0
1.0
1.0
1.0
1.0
0.75
0.5
x
16
1.0
0.75
0.75
1.0
0.75
1.0
0.75
0.25
0.5
0.75
0.5
0.5
32
0.5
0.75
1.0
0.5
64
0.5
0.75
1.0
0.5
Tables 2 and 3 present the success rates for the four different function graphs considered. We observe that higher learning rates generally lead to more successful trials across all function graphs and NN depths. This aligns with previous findings indicating that higher learning rates result in more globally optimal solutions [53, 54]. On the other hand, lower learning rates tend to under-prunt the NNs, resulting inefficient hierarchical structures in terms NN density.
When using high learning rates and low batch sizes, we find that training becomes highly unstable, often leading to NNs failing to achieve 100% validation accuracy for all seed values. Therefore, when training and pruning the NNs for other function graphs, we explore the training regime of high learning rates combined with high batch sizes.
I Unit clustering algorithm
L.1 Clustering algorithm hyper-parameter experiments
In this section, discuss the hyperparameters used in the proposed unit clustering algorithm. These hyperparameters include the distance measure for clustering units, the linkage method in Agglomerative clustering, and the criteria for selecting the optimal number of clusters, The primary criterion for the algorithm's usefulness is its ability to uncover modules and hierarchical structure that resembles the hierarchical modularity of the function when using fixed set of hyperparameters.
We consider the four function graphs mentioned in the main part the paper, which include graphs with input separable sub-functions, reused sub-function both input separable and reused sub- functions, and non-modular function graph. We train and prune wide range of NN architectures for each function graph and pass the resulting sparse NNs through all combinations of the aforementioned
33

---

Algorithm 3: Unit clustering algorithm for given layer
Data: f Iy..., Nr. fm (modularity metric threshold); ; /* Given the feature vectors
Result: Optimal number of clusters, Kj
k 2;
/* Enumerate through different cluster assignments */
while k < N₁ do
Cs - Agg
Agglomerative clustering dendogram cut giving
clusters */
Sk < Metric(Ck);
/* Compute the metric to asses clustering quality */
if S then
Ki k
Find the number clusters with lowest score */
9k
end
1: 1: + 1;
end
sin t- 0:
Zeep t
Ki = 2 or Ki == Ni - or > bm then
Zein & test 2;
/* Run test for single cluster detection */
Zeep t test 1
/* Run test for separate clusters detection */
end
if 7ain sep then
sin 2 scp then
Ki 1:
/+ If either one of the test result is positive +/
else
Ki Ní;
end
end
hyperparameters. We then select the set of hyperparameters that successfully uncover the modular structure for the maximum number of NNs and function graphs.
We employ the Agglomerative clustering method on the feature vectors, initially assigning each unit to its own cluster. In each iteration, two clusters merged into one, and this process continues until all clusters are merged into a single cluster. The specific method used to select the two clusters to merge in each iteration is known the linkage method. We experiment with four types of linkage methods: average, single, complete, and ward. Average linkage selects the two clusters to merge based the minimum average pairwise distance between unit features in the two clusters, while single uses the minimum pairwise distance and complete uses the maximum pairwise distance. Ward linkage selects the two clusters merge based on the cluster variance of the newly formed cluster.
Agglomerative clustering produces multiple cluster assignments depending on the number clusters. Each iteration of the clustering method yields a cluster assignment with different number of clusters, ranging from = 1 to N, where is the number units. To determine the optimal number of clusters, experiment with scoring metrics and select the k value with the best cluster quality at each iteration. Specifically, we explore four different metrics: Silhouette Index [55], CH-index [56], 3. DB-index [57]. and 4. Modularity metric (modified).
From Table we observe that all clustering linkage methods combined with either the modularity metric or Silhouette index perform well. Therefore, we choose the combination of average linkage, cosine distances, and the modularity metric. discard Euclidean distance as the feature vectors are binary, and we select cosine distance over Jaccard distance ensure appropriate clustering even in the presence of noise in the feature vectors. Additionally, we prefer average linkage over complete and single linkage methods to enhance the clustering method's 's robustness noise.
34

---

Table Success rates for different clustering algorithm syper-parameteny on 4 function graphs and NNs with varying widths and depths (Figure 37)
Clustering
Distance
Modularity
Silhouette
CH-Index
DB-Index
Linkage
Measure
metric
dex
Feature vector step size 8
L
Complete
Jaceard
0.99
0.99
0.49
0.49
Single
Jaccard
0.99
0.99
0.49
0.49
Average
Jaccard
0.99
0.99
0.49
0.49
Complete
Cosine
0.99
0.99
0.49
0.49
Single
Cosine
0.99
0.99
0.49
0.49
Average
Cosine
0.99
0.99
0.49
0.49
Complete
Euclidean
0.99
0.99
0.49
0.49
Single
Euclidean
0..9
0.99
0.49
0.49
Average
Euclidean
0.99
0.99
0.49
0.49
Ward
Euclidean
0.99
0.99
0.49
0.49
1.2
Edge cases
In the previous sub-section, we explored different metrics for determining the optimal number of clusters the Agglomerative clustering algorithm. However, three out the four metrics are not applicable when the number of clusters is equal to the number of units or when there is only one cluster. Unfortunately, even the modified modularity metric fails detect these cases accurately.
Let δ be the normalized distance matrix of the unit fea- ture vectors, where the sum of all elements is equal to 1. Consider the units partitioned into l: clusters and matrix A E & where Aij EeEC, Dab represents the
M
Σ i=1
Aa
Σ
Aig
(3)
sum of the distances between all pairs of units in clusters C₁ and Cj. The modularity metric, denoted by M, measures the quality of the partitioning and defined as:
The first term this equation measures the total intra-cluster distance between the unit features while the second term is the expected intra-cluster distance under the null hypothesis that unit distances randomly assigned based joint probabilities in D. negative value of M indicates that pair-wise distance within a cluster is lower than the random baseline.
Graph structures for edge cases: The units within given layer must be in the same cluster if the majority of their outgoing connections lead to the same units in the subsequent layers. That is, if the feature vectors dense if they are sparse but have low pairwise distances. On the other hand, the units must belong separate clusters their outgoing connections predominantly target different units in the later layers. That is, if the unit feature vectors sparse and have high pairwise cosine distances. Surprisingly, despite being at opposite ends of the clustering spectrum, these two cases exhibit highly similar graph structures. In fact, both structures may closely resemble randomly shuffled graphs with the same number of edges as the original graph.
Behavior of the modularity metric: The modularity metric often fails to distinguish between the previously discussed graph structures and struggles to detect them accurately. Specifically, when there is only single cluster (k 1), the modularity metric always yields value of 0, irrespective of the pairwise cosine distances. Similarly, when NN, the modularity metric values (M) are always less than equal to O, regardless of the pairwise cosine distances. Consequently, even a slightly sparse random graph can result in negative modularity metric values for = N (as well as other values).
For instance, consider function graph, neural network, and modularity metric values depicted in Figure 38. In the input layer, the connectivity or unit feature vectors exhibit slight sparsity. Despite the clear expectation that all input units should belong to single cluster, the modularity metric value is the lowest for & 4 N.
35

---

Figure 38: Row 1: a. Function graph with a reused sub-function, b. hierarchically modular structure detected through NN with 3 hidden layers and width of 24. :Row 2: Modularity metric values for various layers and varying number of clusters k
Reused sub-function
GOOOOOO
oparts -45, uss
2
4
Layer
0.0
-0.16
-0,24
-0.26
0.0
-0.5
+0.375
X
3
0.0
-0.5
-0.375
X
0.0
0.5
X
Figure 39: Row 1: Function graph with 3 input separable and reused sub-functions, b. hierarchically modular structure detected through a NN with 3 hidden layers and width of 24. :Row 2: Modularity metric values for various layers and varying number of clusters k
Input separable and reused
Moduisrity2, Archés.
betch
k
3
5
6
Layer
0.0
-0.22
-0.33
-0.28
-0.22
-0.17
2
0.0
-0.22
-0.33
X
X
X
0.0
-0.22
-0.33
X
0.0
-0.22
-0.33
X
36

---

Figure 40: Row 1: a. Function graph with single densely connected sub-function, b. hierarchically modular structure detected through a NN with hidden layers and width of 24. :Row 2: Modularity metric values for various layers and varying number of clusters it
Single sub-function
Modidartyf1l Ard64, 24, 24, 4): Dersity 1.20%
k
1
2
3
Layer
0.0
0.0
0.0
0.0
2
0.0
0.0
0.0
3
0.0
X
X
X
0.0
X
In Figure 39, we can observe that in layers 3, and 4, the modularity metric value is lowest for
k = 3 = N, which aligns with the ground truth. However, due to our previous observation regarding = N consistently yielding the lowest modularity metric value, regardless of the ground truth being k = 1, this becomes unreliable outcome. The fact that l: N always generates negative modularity metric values undermines effectiveness detecting the case where k N.
Lastly, Figure 40 illustrates that if the neural network is densely connected, the modularity metric values for all & O, further complicating the search for an exact solution. As result of these observations, we have developed an additional tool to identify the edge cases of A and k = N.
Unit separability test: The unit separability test is designed to evaluate whether two units in cluster can be separated into sub-clusters. Consider two units and j. with o; = = fi. 0₁ = ES neighbors respectively, and 0ij Sx @ fj common neighbors. We consider random baseline that preserves o and 0j. The number of common neighbors is modeled as binomial random variable with trials and probability of success separable if the observed value of oij is less than the expected value E(oy) under the random model.
g²= where g is the total number of units in the later layer. The units
We can observe in the previous examples that if those edge cases exist in the ground truth, usually A 2 l N has the lowest modularity metric among k .....N
Test 1: Consider the partition where N 1 clusters are obtained. the two units that are found in the same cluster are separable, it implies that all units belong to separate clusters.
Test 2:
Let us consider the partition of units into two clusters. We merge the feature vectors of the two unit groups. If the two groups of units are not separable, it implies that all units must belong to the same cluster.
In some cases, both tests yield positive results as the graph structures are similar (discussed above). We determine the optimal number of clusters by selecting the result that is more statistically significant. The detailed pseudo code for unit clustering is shown in algorithm 3.
37


Reviews:
[{"review_id": "t7o9ssacjY", "reviewer": "Reviewer_Czk6", "summary": "The paper proposes a methodology for uncovering hierarchical modularity in neural networks (NNs). It combines iterative pruning and network analysis to reveal the underlying hierarchy of sub-functions in tasks. The paper demonstrates the effectiveness of the method on both Boolean functions and vision tasks using the MNIST dataset. \n\nThe main contribution of the paper lies in providing a novel approach to uncover hierarchical modularity without prior knowledge of the task's hierarchy. \n\nThe methodology offers insights into efficient and interpretable learning systems and showcases the potential of pruning and network analysis methods in revealing and utilizing structural properties in NNs.", "questions": "1. How does the proposed iterative pruning process affect the overall performance of the neural networks in terms of learning efficiency and accuracy?\n2. Are there any limitations or challenges encountered when applying the proposed methodology to more complex tasks beyond Boolean functions and MNIST digit classification?\n3. Could the approach be extended to tasks with dynamic or evolving hierarchical structures, where the sub-functions change over time?\n4. How does the proposed methodology compare to existing approaches in terms of accuracy, efficiency, and scalability when uncovering hierarchical modularity in neural networks?", "limitations": "Minor comments: \n- Figure 5B1 -> the text is hard to read on a printed paper, due to small fonts in the figure. This is a minor comment, because if one is reading the PDF paperlessly, one can zoom in. ", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "The paper demonstrates a significant strength through its comprehensive experimental evaluation, encompassing modular and hierarchical Boolean function graphs, as well as tasks utilizing the MNIST digits dataset. The authors meticulously conduct numerous trials, systematically varying network parameters like depth, width, and seed values to thoroughly validate the efficacy of their proposed methodology. The experimental results substantiate the approach's ability to precisely uncover the hierarchical and modular structures within the tasks, serving as empirical evidence of the methodology's robustness and broad applicability.", "weaknesses": "One potential weakness of the paper is the limited discussion and analysis of the results regarding the failures or limitations of the proposed methodology. While the experiments highlight the success rates in detecting modules and uncovering hierarchical structures, there is less exploration of cases where the methodology might not perform as well or situations where the detected modules do not align perfectly with the expected sub-functions. A more in-depth analysis of the challenges and limitations of the approach could provide valuable insights for further improvement and understanding.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their constructive comments and appreciate your valuable feedback. Below we provide response to the weaknesses and questions: \n\n**W1: One potential weakness of the paper is the limited discussion and analysis of the results regarding the failures or limitations of the proposed methodology.**\n\nPlease note that the paper clearly identifies some failure cases in the experiments section and appendix sections. However, we acknowledge the importance of providing more in-depth analysis of those cases. To improve the paper, we will extend the appendix sections and update the experiments section in the camera-ready version, offering a more comprehensive examination of the limitations and challenges encountered.\n\n**Q1: How does the proposed iterative pruning process affect the overall performance of the neural networks in terms of learning efficiency and accuracy?**\n\nThe iterative pruning process, combined with cyclic learning rates, is computationally demanding compared to other pruning methods. During each iteration of the pruning process, units and edges are eliminated, which reduces the operation count for each iteration, still the overall cost is larger than training the dense neural network (NN). However, iterative pruning has been shown to produce highly sparse NNs that generalize well compared to other pruning methods (Leslie N Smith et. al. 2017, Alex Renda et. al. 2020). Our objective is to constrain the NNs to utilize as few units and edges as possible while still learning the task well. Further, the algorithm must operate without any prior knowledge of the final NN configurations (width, density). The iterative pruning algorithm is well-suited for this purpose. Improving computational efficiency is a future research direction that is worth exploring. (additionally see response to reviewer znid, W3)\n\nThroughout the pruning process, the validation accuracy is consistently maintained at the same level as the dense NN. When the NN can no longer achieve the desired accuracy, the pruning process is halted, and the algorithm reverts to the previous sparse NN. Despite pruning, the test accuracy remains largely unchanged, primarily due to longer training time (Tian Jin et. al. 2022) and the structure learned by the NNs.\n\n**Q2: Are there any limitations or challenges encountered when applying the proposed methodology to more complex tasks beyond Boolean functions and MNIST digit classification?**\n\nWe focus on Boolean tasks because it is easier to know their correct hierarchical structure (ground truth), which is required for evaluating our methodology. Analyzing the resulting structure of larger models on more complex tasks could be a follow up work.\n\nFor larger networks and complex tasks, it’s possible that NNs may learn numerous functional decompositions for the same task. The proposed pipeline can uncover only one of these decompositions, which could significantly differ from other possible ones.\n\nWe anticipate good structures to be extracted for tasks learned using MLP-based NNs (e.g., simple MLPs, transformers). For CNNs, adapting unit pruning and clustering features for convolutional layers may also pose additional challenges but the methodology is expected to work well for CNNs after appropriate adjustments.\n\n**Q3: Could the approach be extended to tasks with dynamic or evolving hierarchical structures, where the sub-functions change over time?**\n\nIf our interpretation of this question deviates from your intended one, please let us know. In scenarios where tasks vary, leading to evolving hierarchical structures and sub-functions over time, our current method may not be directly applicable. Our approach requires NNs to first learn a task well before pruning, making it less suitable for dynamic task settings. However, exploring this direction in future research could be promising. Limiting the number of units and edges under evolving tasks may naturally promote the reuse of sub-functions (Kashtan et. al. 2007). Dynamic sparse training algorithms (Mostafa et. al. 2019, Evci et. al. 2019) with growing and pruning of edges during training may facilitate such adaptability.\n\n**Q4: How does the proposed methodology compare to existing approaches in terms of accuracy, efficiency, and scalability when uncovering hierarchical modularity in neural networks?**\n\nTo the best of our knowledge, this work is the first to propose a combined training (pruning) and network analysis tool to uncover hierarchical modularity. However, previous works have proposed methods to detect modules in trained NNs without requiring knowledge of sub-functions or data (structural decompositions).\n\nDaniel Filan, Shlomi Hod, and colleagues (Filan et al. 2021, Hod et al. 2022, Casper et al. 2022) employed normalized spectral clustering to globally extract unit clusters and analyze them. Spectral clustering optimizes for N-cuts, measuring internal connectivity against external connectivity of unit clusters. Our experiments with that method suggest that it often does not uncover the expected modules in sparse NNs. This could be attributed to its global nature and the absence of edges between NN units at the same layer.\n\nWatanabe and colleagues (Watanabe et al., 2018; Watanabe, 2019) published a sequence of interesting papers where they utilized layer-wise clustering of units based on incoming and outgoing connectivity. Our method aligns with this class of previous methods. Although we have not directly tested the latter on the pruned NNs, it’s worth noting that they were designed for conventionally trained NNs. In contrast, our method is simpler and more tailored to the pruned NNs we obtain. Due to the limited time available we were unable to make such quantitative comparisons during the rebuttal phase. "}, {"review_id": "oJdNAvjrOp", "reviewer": "Reviewer_fXf6", "summary": "This paper conducts an investigation of hierarchical modularity in neural networks by studying boolean networks. The paper studies simple hierarchically modular boolean functions and learns them using MLPs. It then propose metrics to discover this modularity by examining 1) input separability and 2) reusability of sub-functions. Finally, the paper provides a clustering based method to identify the modules in neural networks applied to arbitrary tasks. ", "questions": "Currently, the experiments on MNIST to verify the method to discover modularity do serve as a proof of concept but more extensive experiments would be needed to confirm the effectiveness of the proposed approach to identify modules in neural networks in general. \n\nIn particular, extensions to CNNs on more realistic image datasets might be very interesting. It might be useful to conduct experiments with a subset of classes from a dataset like CIFAR100 or ImageNet where the superclasses and subclasses often offer some natural opportunities for hierarchical modularity.", "limitations": "N/A", "rating": 8, "confidence": 5, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "1) Clear and scientifically principled investigation into an important yet understudied facet of neural networks \n\n2) Interesting results showing that hierarchical modularity in neural networks often doesn't emerge with standard training but with pruning (both edge and neuron), the sparsity forces the networks to become hierarchically modular. \n\n3) Novel method to find  with some empirical backing ", "weaknesses": "1) The experiments on more realistic datasets e.g. MNIST can be expanded to link the findings of the paper more concretely to what is observed in practice. \n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the constructive comments about this work.\n\n**Weakness: Currently, the experiments on MNIST to verify the method to discover modularity do serve as a proof of concept but more extensive experiments would be needed to confirm the effectiveness of the proposed approach to identify modules in neural networks in general. In particular, extensions to CNNs on more realistic image datasets might be very interesting. It might be useful to conduct experiments with a subset of classes from a dataset like CIFAR100 or ImageNet where the superclasses and subclasses often offer some natural opportunities for hierarchical modularity**\n\nThe primary aim of this paper is to understand the conditions under which a neural network will acquire a hierarchically modular structure that reflects the functional structure of the given task – and to design a methodology for uncovering that structure. To validate this approach, tasks with known hierarchical structures are needed. Boolean functions offered a diverse range of tasks with distinct structures, allowing for an effective evaluation of the proposed methodology. Additionally, as the reviewer points out, the MNIST experiments provide a proof of concept for relatively larger-scale applicability.\n\nWhile we acknowledge the potential for broader experiments involving larger models and complex tasks like CNNs or transformers, that would be a highly intriguing future research direction that is naturally a follow-up work to this first study.\n\nWe hope this perspective resonates with the reviewer's understanding.\n"}, {"review_id": "02xhZILtlZ", "reviewer": "Reviewer_znid", "summary": "When conventionally trained, neural networks do not demonstrate structural properties like input separable functions or reusability of sub-modules. The authors investigated this phenomenon and proposed iterative pruning to enhance structural properties of neural networks. They demonstrate the effectiveness of their method on boolean functions and a modified MNIST dataset.", "questions": "* Figure 3 and Figure 4 seem to have the exact same titles and captions. Should distinguish them more clearly.\n* I'm not very sure about your definition of reusability (your definition sounds more like \"shared features\" to me). An example I would count as reuse of submodule is: consider input (x1, x2), output ((x1-x2)^2, (x1+x2)^2), the squared function should be learned twice (reused). However, there is probably no shared feature in a trained network. A trained network (e.g., a fully-connected network) can only learn the squared function twice and independently, even with your pruning strategy I guess.\n* Do you expect your method to generalize to larger models, e.g., large language models?", "limitations": "None", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "* The paper is well-written with nice motivations and clear logical flow. \n* The paper investigates this interesting scientific question \"whether conventionally trained neural networks display structural properties\", which is an important question for network interpretability\n* The paper proposes iterative pruning to enhance structural properties, which is a technical contribution.", "weaknesses": "* The scope is a bit limited. The paper only discusses two properties, input separable functions and reuse of sub-modules. The examples are a bit too simple. Said so, maybe this is not too much of a problem for a scientific paper whose goal is to understand something. Still, I'd love to see your method applied to larger-scale experiments.\n* The novelty is not very clear to me. I'm glad to see that iterative pruning works pretty well for module reuse, but it seems there is not too many technical contribution. I suggest authors should highlight the technical contributions/comparisons to previous works.\n* Regarding the method, I feel encouraging modularity directly in training (e.g., adding Eq. (2) as a penalty in training) may further enhance structural properties. I'd love to see how this trick changes the outcomes (especially for the failed cases).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their constructive comments. We provide responses to the identified weaknesses and questions raised next: \n\n**W1: The scope is a bit limited. The paper only discusses two properties, input separable functions and reuse of sub-modules. The examples are a bit too simple.This is not too much of a problem for a scientific paper whose goal is to understand something.**\n\nAs the reviewer also pointed out, the goal of the paper is to understand under which training constraints neural networks (NNs) acquire the hierarchically modular structure reflecting that of the given task – and it proposes a methodology to uncover that structure. The use of simple Boolean function graphs and sub-function properties allows for a principled analysis, making it easier to gain insights into the resulting NN structure. Further, the evaluation of the proposed training and network analysis methodology requires the knowledge of the task’s structure (ground truth). Boolean functions allow us to construct a wide range of tasks with different (yet known) hierarchical structures for detailed evaluation as demonstrated in section 5. Whether properties other than input separability and module reuse are similarly discoverable through our proposed methodology remains to be investigated in future work. However, we believe that these two properties are both quite central and general.\n\n**W2: The novelty is not very clear to me. I'm glad to see that iterative pruning works pretty well for module reuse, but it seems there is not too many technical contributions. I suggest authors should highlight the technical contributions/comparisons to previous works.**\n\nWe would like to highlight the technical contributions in our work:\n\n1. Propose a novel training methodology based on iterative pruning of units and then edges that results in NNs with a hierarchically modular structure that reflects the corresponding structure of the given task.\n2. Develop a method based solely on unit connectivity to organize units remaining after pruning into modules and infer the hierarchical structure learned. The method utilizes path-based unit features, clustering, and cluster merging to uncover the underlying hierarchy of modules. \n3. Design experiments and analysis tools to detect whether NNs, after training, acquire structural properties resembling the properties of the task’s sub-functions. \n4. While individual components of our proposed training (pruning) and module detection methodology have been previously explored, our main contribution is to synthesize these components into a coherent and empirically evaluated pipeline.\n\nTo the best of our knowledge, our paper is the first work that presents a combined training (pruning) and network analysis tool (module detection) to uncover hierarchical modularity. Previous works in modularity and NNs have only worked on the latter. Due to page limitations, we combined comparisons with previous works in the introduction section (paragraph 2). That paragraph provides a high level overview of prior work and differences with our paper. We will include a more detailed comparison at a technical level in the camera-ready version, using the additional page provided.\n\n**W3: I feel encouraging modularity directly in training (e.g., adding Eq. (2) as a penalty in training) may further enhance structural properties.**\n\nThank you for this very interesting suggestion. The concept of hierarchical modularity naturally incorporates sparsity and reusability, resulting in more efficient task/function representations. Our pruning approach revolves around the idea of first restricting the number of units to promote module reuse and then the number of edges to reveal the sparse connectivity, thus promoting the emergence of hierarchical modularity.\n\nAdding a penalty term to the loss function to restrict the number of units and edges is a promising idea. However, it requires careful consideration, including the sequential nature of unit and edge penalty application (refer to section 3) to capture densely connected reused modules effectively. We acknowledge the potential of this approach to reduce training costs. It is a future research direction that is definitely worth exploring.\n\n**Q1: Figures 3 and 4 seem to have the exact same titles and captions.**\n\nWe will make the figure titles and captions more distinguishable in the final version.\n\n**Q2: I'm not very sure about your definition of reusability. An example I would count as reuse is: consider input (x1, x2), output ((x1-x2)^2, (x1+x2)^2), the squared function should be reused. A trained network can only learn the squared function twice and independently, even with your pruning strategy.**\n\nWe want to clarify the distinction between function reuse and operation reuse, as we define them in this work. In the example provided, squaring is an operation that is independent of its input variables. On the other hand, a function is a combination of such operations along with specific ordered input variables to it. As correctly pointed out, specific operations have to be relearned if applied to different inputs due to the fixed data flow in NNs. In systems with dynamic routing, it would be possible to learn squaring only once, qualifying as a reused operation. However, in fixed graphs like NNs, this is not feasible, as also highlighted in prior works (Gref et. al. 2020, Csordas et. al. 2021). We will clarify this distinction and elaborate on it in the next version of the paper.\n\n**Q3: Do you expect your method to generalize to larger models?**\n\nWe expect the overall idea of restricting the number of units and edges (see W3) to remain valid. We do hope to apply our method to larger models and analyze the resulting structure. However, this remains out of scope for this work as the hierarchical structure of those tasks is unknown (see W1) and any identified structure couldn’t be compared against a ground truth."}]

Author rebuttal:
We would like to thank all reviewers for their comments, time and effort. We have carefully thought about and responded to individual reviews, focusing on the weaknesses pointed out and the questions asked. If additional details, explanations, or clarifications are needed, we will be happy to provide them. 

Meta-review: This paper proposes a new method for uncovering hierarchical modularity in neural networks. It combines iterative pruning and network analysis to reveal the underlying hierarchy of sub-functions in tasks. Experiments are conducted on Boolean functions and a modified MNIST dataset.

After rebuttal, it received scores of 678. All the reviewers agree that (1) this paper provides a novel method to uncover hierarchical modularity without prior knowledge of the task's hierarchy. It provides clear and scientifically principled investigation into an important yet understudied facet of neural networks. (2) Experiments are convincing, which show the potential of pruning and network analysis methods to force neural networks to become hierarchically modular. On the other hand, a shared concern by the three reviewers is that the experiments on MNIST is more like a proof of concept. Because of this, I cannot push this accept to a spotlight. Analyzing the resulting structure of larger models on more complex tasks could be a very interesting follow up work.

Overall, given the general positive review feedback, the AC would like to recommend acceptance of the paper.
Decision: Accept (poster)