Year: 2019

Abstract:
The output of a neural network depends on its parameters in a highly nonlinear way, and it is widely assumed that a network’s parameters cannot be identified from its outputs. Here, we show that in many cases it is possible to reconstruct the architecture, weights, and biases of a deep ReLU network given the ability to query the network. ReLU networks are piecewise linear and the boundaries between pieces correspond to inputs for which one of the ReLUs switches between inactive and active states. Thus, first-layer ReLUs can be identified (up to sign and scaling) based on the orientation of their associated hyperplanes. Later-layer ReLU boundaries bend when they cross earlier-layer boundaries and the extent of bending reveals the weights between them. Our algorithm uses this to identify the units in the network and weights connecting them (up to isomorphism). The fact that considerable parts of deep networks can be identified from their outputs has implications for security, neuroscience, and our understanding of neural networks.

heading: 1 INTRODUCTION
text: The behavior of deep neural networks is as complex as it is powerful. The relation of individual parameters to the network’s output is highly nonlinear and is generally unclear to an external observer. Consequently, it has been widely supposed in the field that it is impossible to recover the parameters of a network merely by observing its output on different inputs.
Beyond informing our understanding of deep learning, going from function to parameters could have serious implications for security and privacy. In many deployed deep learning systems, the output is freely available, but the network used to generate that output is not disclosed. The ability to uncover a confidential network not only would make it available for public use but could even expose data used to train the network if such data could be reconstructed from the network’s weights.
This topic also has implications for the study of biological neural networks. Experimental neuroscientists can record some variables within the brain (e.g. the output of a complex cell in primary visual cortex) but not others (e.g. the pre-synaptic simple cells), and many biological neurons appear to be well modeled as the ReLU of a linear combination of their inputs (Chance et al., 2002). It would be highly useful if we could reverse engineer the internal components of a neural circuit based on recordings of the output and our choice of input stimuli.
In this work, we show that it is, in fact, possible in many cases to recover the structure and weights of an unknown ReLU network by querying it. Our method leverages the fact that a ReLU network is piecewise linear and transitions between linear pieces exactly when one of the ReLUs of the network transitions from its inactive to its active state. We attempt to identify the piecewise linear surfaces in input space where individual neurons transition from inactive to active. For neurons in the first layer, such boundaries are hyperplanes, for which the equations determine the weights and biases of the first layer (up to sign and scaling). For neurons in subsequent layers, the boundaries are “bent hyperplanes” that bend where they intersect boundaries associated with earlier layers. Measuring these intersections allows us to recover the weights between the corresponding neurons.
Our major contributions are:
• We identify how the architecture, weights, and biases of a network can be recovered from the arrangement of boundaries between linear regions in the network.
• We implement this procedure and demonstrate its success in recovering trained and untrained ReLU networks. • We show that this algorithm “degrades gracefully,” providing partial weights even when full

heading: 2 RELATED WORK
text: Various works within the deep learning literature have considered the problem of learning a network given its output on inputs drawn (non-adaptively) from a given distribution. It is known that this problem is in general hard (Goel et al., 2017), though positive results have been found for certain specific choices of distribution in the case that the network has only one or two layers (Ge et al., 2019; Goel & Klivans, 2017). By contrast, we consider the problem of learning about a network of arbitrary depth, given the ability to issue queries at specified input points. In this work, we leverage the theory of linear regions within a ReLU network, an area that has been studied e.g. by Telgarsky (2015); Raghu et al. (2017); Hanin & Rolnick (2019a). Most recently Hanin & Rolnick (2019b) considered the boundaries between linear regions as arrangements of “bent hyperplanes”. Milli et al. (2019); Jagielski et al. (2019) show the effectiveness of this strategy for networks with one hidden layer. For inference of other properties of unknown networks, see e.g. Oh et al. (2019).
Neuroscientists have long considered similar problems with biological neural networks, albeit armed with prior knowledge about network structure. For example, it is believed that complex cells in the primary visual cortex, which are often seen as translation-invariant edge detectors, obtain their invariance through what is effectively a two-layer neural network (Kording et al., 2004). A first layer is believed to extract edges, while a second layer essentially implements maxpooling. Heggelund (1981) perform physical experiments akin to our approach of identifying one ReLU at a time, by applying inputs that move individual neurons above their critical threshold one by one. Being able to solve such problems more generically would be useful for a range of neuroscience applications.

heading: 3 PRELIMINARIES

heading: 3.1 DEFINITIONS
text: In general, we will consider fully connected, feed-forward neural networks (multilayer perceptrons) with ReLU activations. Each such network N defines a function N (x) from input space Rnin to output space Rnout . We denote the layer widths of the network by nin (input layer), n1, n2, . . . , nd, nout (output layer). We use Wk to denote the weight matrix from layer (k − 1) to layer k, where layer 0 is the input; and bk denotes the bias vector for layer k. Given a neuron z in the network, we use z(x) to denote its preactivation for input x ∈ Rnin . Thus, for the jth neuron in layer k, we have
zkj (x) = nk−1∑ i=1 Wkij ReLU(z k−1 i (x) + b k i ).
For each neuron z, we will use Bz to denote the set of x for which z(x) = 0. In general1, Bz will be an (nin−1)-dimensional piecewise linear surface in Rnin (see Figure 1, in which input dimension is 2 and the Bz are simply lines). We call Bz the boundary associated with neuron z, and we say that B = ⋃ Bz is the boundary of the overall network. We refer to the connected components of Rnin \B as regions. Throughout this paper, we will make the Linear Regions Assumption: The set of regions is the set of linear pieces of the piecewise linear function N (x). While this assumption has tacitly been made in the prior literature, it is noted in Hanin & Rolnick (2019b) that there are cases where it does not hold – for example, if an entire layer of the network is zeroed out for some inputs.

heading: 3.2 ISOMORPHISMS OF NETWORKS
text: Before showing how to infer the parameters of a neural network, we must consider to what extent these parameters can be inferred unambiguously. Given a network N , there are a number of other networks N ′ that define exactly the same function from input space to output space. We say that such networks are isomorphic to N . For multilayer perceptrons with ReLU activation, we consider the following network isomorphisms:
Permutation. The order of neurons in each layer of a network N does not affect the underlying function. Formally, let pk,σ(N ) be the network obtained fromN by permuting layer k according to σ (along with the corresponding weight vectors and biases). Then, pk,σ(N ) is isomorphic to N for every layer k and permutation σ.
Scaling. Due to the ReLU’s equivariance under multiplication, it is possible to scale the incoming weights and biases of any neuron, while inversely scaling the outgoing weights, leaving the overall function unchanged. Formally, for z the ith neuron in layer k and c any positive constant, let sz,c(N ) be the network obtained from N by replacing Wk·i, bki , and Wk+1 by cWk·i, cbki , and (1/c)W k+1 i· , respectively. It is simple to prove that sz,c(N ) is isomorphic to N (see Appendix A). Thus, we can hope to recover a network only up to layer-wise permutation and neuron-wise scaling. Formally, pi,σ(N ) and sz,c(N ) are generators for a group of isomorphisms of N . (As we shall see in §5, some networks also possess additional isomorphisms.)

heading: 4 THE ALGORITHM

heading: 4.1 INTUITION
text: Consider a network N and neuron z ∈ N , so that Bz is the boundary associated with neuron z. Recall that Bz is piecewise linear. We say that Bz bends at a point if Bz is nonlinear at that point (that is, if the point lies on the boundary of several regions). As observed in Hanin & Rolnick (2019b), Bz can bend only at points where it intersects boundaries Bz′ for z′ in an earlier layer of
1More precisely, this holds for all but a measure zero set of networks, and any network for which this is not true may simply be perturbed slightly.
the network. In general, the converse also holds; Bz bends wherever it intersects such a boundary Bz′ (see Appendix A). Then, for any two boundaries Bz and Bz′ , one of the following must hold: Bz bends at their intersection (in which case z occurs in a deeper layer of the network), Bz′ bends (in which case z′ occurs in a deeper layer), or neither bends (in which case z and z′ occur in the same layer). It is not possible for both Bz and Bz′ to bend at their intersection – unless that intersection is also contained in another boundary, which is vanishingly unlikely in general. Thus, the architecture of the network can be determined by evaluating the boundaries Bz and where they bend in relation to one another.
Moving beyond architecture, the weights and biases of the network can also be determined from the boundaries, one layer at a time. Boundaries for neurons in the first layer do not bend and are simply hyperplanes; the equations of these hyperplanes expose the weights from the input to the first layer (up to permutation, scaling, and sign). For each subsequent layer, the weight between neurons z and z′ can be determined by calculating how Bz′ bends when it crosses Bz . The details of our algorithm below are intended to make these intuitions concrete and perform efficiently even when the input space is high-dimensional.
Algorithm 1 The first layer Initialize P1 = P2 = S1 = {} for t = 1, . . . , L do
Sample line segment ` P1 ← P1 ∪ PointsOnLine(`)
end for for p ∈ P1 do
H = InferHyperplane(p) if TestHyperplane(H) then
S1 ← S1 ∪ GetParams(H) else P2 ← P2 ∪ {p} end if
end for return Parameters S1,
unused sample points P2
Algorithm 2 Additional layers Input Pk and S1, . . . , Sk−1 Initialize Sk = {} for p1 ∈ Pk−1 on boundary Bz do
Initialize Az = {p1}, Lz = Hz = {} while Lz 6⊇ Layer k − 1 do
Pick pi ∈ A and v p′, Bz′ = ClosestBoundary(pi,v) if p′ on boundary then
Az ← Az ∪ {p′ + } Lz ← Lz ∪ {z′} Hz ← Hz ∪ {InferHyperplane(pi)}
else Pk ← Pk ∪ {p1}; break end if
end while if Lz ⊇ Layer k − 1 then Sk ← GetParams(Tz) end if
end for return Parameters Sk, unused sample points Pk+1

heading: 4.2 THE FIRST LAYER
text: We begin by identifying the first layer of the network N , for which we must infer the number of neurons, the weight matrix W1, and the bias vector b1. As noted above, for each z = z1i in the first layer, the boundary Bz is a hyperplane with equation W1·ix+ b 1 i = 0. For each neuron z in a later layer of the network, the boundaryBz will, in general, bend and not be a (complete) hyperplane (see Appendix A). We may therefore find the number of neurons in layer 1 by counting the hyperplanes contained in the network’s boundary B, and we can infer weights and biases by determining the equations of these hyperplanes.
Boundary points along a line. Our algorithm is based upon the identification of points on the boundary B. One of our core algorithmic primitives is a subroutine PointsOnLine that takes as input a line segment ` ⊂ Rnin and approximates the set ` ∩ B of boundary points along `. The algorithm proceeds by leveraging the fact that boundary points subdivide ` into regions within which N (x) is linear. We maintain a list of points in order along ` (initialized to the endpoints and midpoint of `) and iteratively perform the following operation: For each three consecutive points on our list, x1,x2,x3, we determine if the vectors (N (x2)−N (x1))/||x2−x1||2 and (N (x3)−N (x2))/||x3− x2||2 are equal (to within computation error) – if so, we remove the point x2 from our list, otherwise we add the points (x1 + 2x2)/3 and (x3 + 2x2)/3 to our list.2 The points in the list converge by binary search to the set of discontinuities of the gradient ∂N (x)/∂x, which are our desired boundary points. Note that PointsOnLine is where we make use of our ability to query the network.
2These weighted averages speed up the search algorithm by biasing it towards points closer towards the center of the segment, which is where we expect the most intersections given our choice of segments.
Sampling boundary points. In order to identify the boundaries Bz for z in layer 1, we begin by identifying a set of boundary points with at least one on each Bz . A randomly chosen line segment through input space will intersect some of the Bz – indeed, if it is long enough, it will intersect any fixed hyperplane with probability 1. We sample line segments ` in Rnin and run PointsOnLine on each. Many sampling distributions are possible, but in our implementation we choose to sample segments of fixed (long) length, tangent at their midpoints to a sphere of fixed (large) radius. This ensures that each of our sample lines remains far from the origin, where boundaries are in closer proximity and therefore more easily confused with one another (this will become useful in the next step). Let P1 be the overall set of boundary points identified on our sample line segments.
Inferring hyperplanes. We now proceed to fit a hyperplane to each of the boundary points we have just identified. For each p ∈ P1, there is a neuron z such that p lies on Bz . The boundary Bz is piecewise linear, with nonlinearities only along other boundaries, and with probability 1, p does not lie on a boundary besides Bz . Therefore, within a small enough neighborhood of p, Bz is given by a hyperplane, which we call the local hyperplane at p. If z is in layer 1, then Bz equals the local hyperplane. The subroutine InferHyperplane takes as input a point p on a boundary Bz and approximates the local hyperplane within which p lies. This algorithm proceeds by sampling many small line segments around p, running PointsOnLine to find their points of intersection withBz , and performing a linear regression to find the equation of the hyperplane containing these points.
Testing hyperplanes. Not all of the hyperplanes we have identified are actually boundaries for neurons in layer 1, so we need to test which hyperplanes are contained in B in their entirety, and which are the local hyperplanes of boundaries that bend. The subroutine TestHyperplane takes as input a point p and a hyperplane H containing that point, and determines whether the entire hyperplane H is contained in the boundary B of the network. This algorithm proceeds by sampling points within H that lie far from p and applying PointsOnLine to a short line segment around each such point to check whether these points all lie on B. Applying TestHyperplane to those hyperplanes inferred in the preceding step allows us to determine those Bz for which z is in layer 1.
From hyperplanes to parameters. Finally, we identify the first layer of N from the equations of hyperplanes contained in B. The number of neurons in layer 1 is given simply by the number of distinct Bz which are hyperplanes. As we have observed, for z = z1i in layer 1, the hyperplane Bz is given by W1·ix+ b 1 i = 0. We can thus determine W 1 ·i and b 1 i up to multiplication by a constant. However, we have already observed that scaling W1·i and b 1 i by a positive constant (while inversely scaling W2i·) is a network isomorphism (§3.2). Therefore, we need only determine the true sign of the multiplicative constant, corresponding to determining which side of the hyperplane is zeroed out by the ReLU. This determination of sign will be performed below in §4.3. Sample complexity. We expect the number of queries necessary to obtain weights and biases (up to sign) for the first layer should grow as O(nin( ∑ i ni) log n1), which for constant-width networks is only slightly above the number of parameters being inferred. Assuming that biases in the network are bounded above, each sufficiently long line has at least a constant probability of hitting a given hyperplane, suggesting that log n1 lines are required according to a coupon collector-style argument. Hanin & Rolnick (2019a) show that under natural assumptions, the number of boundary points intersecting a given line through input space grows linearly in the total number of neurons in the network. Finally, each boundary point on a line requires O(nin) queries in order to fit a hyperplane.

heading: 4.3 ADDITIONAL LAYERS
text: We now assume that the weights W1, . . . ,Wk−1 and biases b1, . . . ,bk−1 have already been determined within the network N , with the exception of the sign choice for weights and biases at each neuron in layer k− 1. We now show how it is possible to determine the weights Wk and biases bk, along with the correct signs for Wk−1 and bk−1.
Closest boundary along a line. In this part of our algorithm, we will need the ability to move along a boundary to its intersection with another boundary. For this purpose, the subroutine ClosestBoundary will be useful. It takes as input a point p, a vector v and the network parameters as determined up to layer k − 1, and outputs the smallest c > 0 such that q = p+ cv lies on Bz for some z in layer at most k − 1. In order to compute c, we consider the region R within which p lies, which is associated with a certain pattern of active and inactive ReLUs. For each boundary Bz , we can calculate the hyperplane equation which would define Bz were it to intersect R, due to the fixed pattern of active and inactive neurons withinR, and we can calculate the distance
from p to this hyperplane. While not every boundary Bz intersects R, the closest boundary does, allowing us to find the desired c.
Unused boundary points. In order to identify the boundaries Bz for z in layer k, we wish to identify a set of boundary points with at least one on each such boundary. However, in previous steps of our algorithm, a set Pk−1 of boundary points was created, of which some were used in ascertaining the parameters of earlier layers. We now consider the subset Pk ⊂ Pk−1 of points that were not found to belong to Bz , for z in layers 1 through k− 1. These points have already had their local hyperplanes determined.
Exploring boundary intersections. Consider a point p1 ∈ Pk such that p1 ∈ Bz . Note that Bz will, in general, have nonlinearities where it intersects each Bz′ for which z′ lies in an earlier layer than z. We explore these intersections, and in particular attempt to find a point ofBz ∩Bz′ for every z′ in layer k − 1. Given the local hyperplane H at p1, we pick a direction v along H and apply ClosestBoundary to calculate the closest point of intersection p′ with Bz′ for all z′ already identified in the network. (Below we discuss how best to pick v.) Note that if z is in layer k, then p′ must be on Bz as well as Bz′ , while if z is in a later layer of the network, then there may exist unidentified neurons in layers below z and therefore Bz may bend before meeting Bz′ . We check if p′ lies on Bz by applying PointsOnLine, and if so apply InferHyperplane to calculate the local hyperplane of Bz on the other side of Bz′ from p1. We select a representative point p2 on this local hyperplane. We repeat the process of exploration from the points p1,p2, . . . until one of the following occurs: (i) a point of Bz ∩Bz′ has been identified for every z′ in layer k− 1 (this may be impossible; see §5), (ii) z is determined to be in a layer deeper than k (as a result of p′ not lying on Bz), or (iii) a maximum number of iterations has been reached.
How to explore. An important step in our algorithm is exploring points of Bz that lie on other boundaries. Given a set of points Az = {p1,p2, . . . ,pm} on Bz , we briefly consider several methods for picking a point pi and direction v along the local hyperplane at pi to apply ClosestBoundary. One approach is to pick a random point pi from those already identified and a random direction v; this has the advantage of simplicity. However, it is somewhat faster to consider for which z′ the intersectionBz∩Bz′ has not yet been identified and attempt specifically to find points on these intersections. One approach for this is to pick a missing z′ and identify for which pi the boundary Bz′ lies on the boundary of the region containing pi and solve a linear program to find v. Another approach is to pick a missing z′ and a point pi, calculate the hyperplane H which would describeBz′ under the activation pattern of pi, and choose v along the local hyperplane to pi such that the distance toH is minimized. This is the approach which we take in our implementation, though more sophisticated approaches may exist and present an interesting avenue for further work.
From boundaries to parameters. We now identify layer k ofN , along with the sign of the parameters of layer k−1, by measuring the extent to which hyperplanes bend at their intersection. We are, in addition, able to identify the correct signs at layer k − 1 by solving an overconstrained system of constraints capturing the influence of neurons in layer k− 1 on different regions of input space. The following theorem formalizes the inductive step that allows us to go from what we know at layer k − 1 (weights and biases, up to scaling and sign) to the equivalent set of information for layer k, plus filling in the signs for layer k − 1. The proof is given in Appendix B. Theorem. The following holds true for deep multi-layer perceptronsN satisfying the Linear Region Assumption (§3.1), excluding a set of networks with measure zero: Suppose that the weights and biases ofN are known up through layer k− 1, with the exception that for each neuron in layer k − 1, the sign of the incoming weights and the bias is unknown. Suppose also that for each z in layer k, there exists an ordered set of points Az = {p1,p2, . . . ,pm} such that: (i) Each point lies on the boundary of Bz , and in (the interior of) a distinct region with respect to the earlier-layer boundaries already known; (ii) each point (except for p1) has a precursor in an adjacent region; (iii) for each such pair of points, the local hyperplanes of Bz are known, as is the boundaryBz′ dividing them (z′ in an earlier layer); (iv) the set of such z′ includes all of layer k−1. Then, it is possible to recover the weights and biases for layer k, with the exception that for each neuron, the sign of the incoming weights and the bias is unknown. It is also possible to recover the sign for every neuron in layer k − 1.
Note that even when assumption (iv) of the Theorem is violated, the algorithm recovers the weights corresponding to whichever boundaries are successfully crossed (as we verify empirically in §6).

heading: 5 DISCUSSION
text: We here explore some reasons why our algorithm may fail, motivate our recursive approach, and discuss the potential for generalizations to different architectures.
Non-intersecting boundaries. It is possible that for some neurons z and z′ in consecutive layers, there is no point of intersection between the boundaries Bz and Bz′ (or that this intersection is very small), making it impossible to infer the weight between z and z′ by our algorithm. Some such cases represent an ambiguity in the underlying network – an additional isomorphism to those described in §3.2. Namely, Bz ∩ Bz′ is empty if one of the following cases holds: (1) whenever z is active, z′ is inactive; (2) whenever z is active, z′ is active; (3) whenever z is inactive, z′ is inactive; or (4) whenever z is inactive, z′ is active. In case 1, observe that a slight perturbation to the weight w between z and z′ has no effect upon the network’s output; thus w is not uniquely determined. Cases 2-4 present a more complicated picture; depending on the network, there may or may not be additional isomorphisms.
Boundary topology. For simplicity in our algorithm, we have not considered the relatively rare cases where boundaries Bz are disconnected or bounded. If Bz is disconnected, then it may not be possible to find a connected path along it that intersects all boundaries arising from the preceding layer. In this case, it is simple to infer that two independently identified pieces of the boundary belong to the same neuron to infer the full weight vector. Next, if Bz is bounded for some z, then it is a closed (d − 1)-dimensional surface within d-dimensional input space3. While our algorithm requires no modification in this case, bounded Bz may be more difficult to find by intersection with randomly chosen lines, and a more principled sampling method may be helpful.
Our recursive approach. Our approach proceeds layer by layer, leveraging the fact that each boundary bends only those for those boundaries corresponding to earlier neurons in the network. Our approach in the first layer is, however, distinct from (and simpler than) the algorithm for subsequent layers. One might wonder why, once the first k − 1 layers have been identified, it is not possibly simply to apply our first-layer algorithm to the nk−1-dimensional “input space” arising from activations of layer k − 1. Unfortunately, this is not possible in general, as this would require the ability to evaluate layer k for arbitrary settings of layer k− 1. ReLU networks are hard to invert, and therefore it is unclear how one could manufacture an input for a specified layer k− 1 activation, even while knowing the parameters for the first k − 1 layers. Other architectures. While we have expressed our algorithm in terms of multilayer perceptrons with ReLU activation, it also extends to various other architectures of neural network. Other piecewise linear activation functions admit similar algorithms. For a network with convolutional layers, it is possible to use the same approach to infer the weights between neurons, with two caveats: (i) As we have stated it, the algorithm does not account for weight-sharing – the number of “neurons” in each layer is thus dependent on the input size, and is very large for reasonably sized images. (ii) Pooling layers do affect the partition into activation regions, and indeed introduce new discontinuities into the gradient; our algorithm therefore does not apply. For skip connections as in ResNets (He et al., 2016), our algorithm holds with slight modification, which we defer until future work.

heading: 6 EXPERIMENTS
text: We verified the success of our algorithm on both untrained and trained networks. In keeping with literature on ReLU network initialization (He et al., 2015; Hanin & Rolnick, 2018), networks were initialized using i.i.d. normal weights with variance 2/fan-in and i.i.d. normal biases with unit variance. We trained networks on either the MNIST dataset or a memorization task of 1000 “datapoints” of dimension 10 with coordinates drawn i.i.d. from a unit Gaussian and given arbitrary binary labels. Training was performed using the Adam optimizer and a cross-entropy loss applied to the softmax of the final layer, over 20 epochs for MNIST and 1000 epochs for the memorization task. The trained networks (when sufficiently large) were able to attain near-perfect accuracy. We observed that both the first-layer algorithm and additional-layer algorithm identified weights and biases to within extremely high accuracy (see Figures 3 and 4). Even in cases where, for the additional-layer algorithm, a small fraction of neurons were not identified (see §5), the algorithm was able to correctly predict the remaining parameters.
3For 2D input, such Bz must be topological circles, but for higher dimensions, it is conceivable for them to be more complicated surfaces, such as toroidal polyhedra.

heading: 7 CONCLUSION
text: In this work, we have shown that it is often possible to recover the architecture, weights, and biases of deep ReLU networks by repeated queries. We proceed by identifying the boundaries between linear regions of the network and the intersections of these boundaries. Our approach is theoretically justified and empirically validated on networks before and after training. Where the algorithm does not succeed in giving a complete set of weights, it is nonetheless able to give a partial set of weights, and incompleteness in some cases reflects unresolvable ambiguities about the network.
Our approach works for a wide variety of networks, though not all. It is limited to ReLU or otherwise piecewise linear activation functions, though we believe it possible that a continuous version of this method could potentially be developed in future work for use with sigmoidal activation. If used with convolutional layers, our method does not account for the symmetries of the network and therefore scales with the size of the input as well as the number of features, resulting in high computation. Finally, the method is not robust to defenses such as adding noise to the outputs of the network, and therefore can be thwarted by a network designer that seeks to hide their weights/architecture.
We believe that the methods we have introduced here will lead to considerable advances in identifying neural networks from their outputs, both in the context of deep learning and, more speculatively, in neuroscience. While the implementation we have demonstrated here is effective in small instances, we anticipate future work that optimizes these methods for efficient use with different architectures and at scale.

heading: A USEFUL LEMMATA
text: Lemma 1 (Isomorphism under scaling). Given an MLP N with ReLU activation, the network sz,c(N ) is isomorphic to N for every neuron z and constant c > 0.
Proof. Suppose that z = zki is the ith neuron in layer k. Then, for each neuron z k+1 j in layer k + 1 of the network N , we have:
zk+1j (x) = nk∑ i=1 Wkij ReLU(z k i (x) + b k i )
= nk∑ i=1 Wkij ReLU (( nk−1∑ h=1 Wk−1hi ReLU(z k−1 h (x) + b k−1 h ) ) + bki ) (1)
By comparison, in network sz,c(N ), we have:
zk+1j (x) = nk∑ i=1 1 c Wkij ReLU(z k i (x) + cb k i )
= nk∑ i=1 1 c Wkij ReLU (( nk−1∑ h=1 cWk−1hi ReLU(z k−1 h (x) + b k−1 h ) ) + cbki )
= nk∑ i=1 Wkij ReLU (( nk−1∑ h=1 Wk−1hi ReLU(z k−1 h (x) + b k−1 h ) ) + bki ) , (2)
where we used the property that ReLU(cx) = cReLU(x) for any c > 0.
As expressions (1) and (2) are equal, we conclude that sz,c(N ) is isomorphic to N .
Lemma 2 (Bending hyperplanes). The set of networks N with the following property has measure zero in the space of networks: There exist neurons zk−1i and z k j in consecutive layers such that the boundary Bzkj intersects Bzk−1i but does not bend at the intersection.
Proof. Observe that Bzkj is defined by the equation:
0 = zkj (x) = nk−1∑ h=1 Wkhj ReLU(z k−1 h (x) + b k−1 h ).
As it does not bend when it intersects Bzk−1i , the gradient of the RHS must remain unchanged when ReLU(zk−1i (x) + b k−1 i ) flips between active and inactive. Unless another neuron transitions simultaneously with zk−1i (an event that occurs with measure zero), this can happen only if W k ij = 0, which itself is a measure zero event.

heading: B PROOF OF THEOREM
text: In this proof, we will show how the information we are given by the assumptions of the theorem is enough to recover the weights and biases for each neuron z in layer k. We will proceed for each z individually, progressively learning weights between z and each of the neurons in the preceding layer (though for skip connections this procedure could also easily be generalized to learn weights from z to earlier layers).
For each of the points pi ∈ Az , suppose that Hi is the local hyperplane associated with pi on boundaryBz . The gradient ∂z∂x (pi) at pi is orthogonal toHi, and we thus already know the direction of the gradient, but its magnitude is unknown to us. We will proceed in order through the points p1,p2, . . . ,pm, with the goal of identifying ∂z∂x (pi) for each pi, up to a single scaling factor, as this computation will end up giving us the incoming weights for z.
We begin with p1 by assigning ∂z∂x (p1) arbitrarily to either one of the two unit vectors orthogonal to Hi. Due to scaling invariance (Lemma 1), the weights of N can be rescaled without changing the function so that ∂z∂x (pi) is multiplied by any positive constant. Therefore, our arbitrary choice can be wrong at most in its sign, and we need not determine the sign at this stage. Now, suppose towards induction that we have identified ∂z∂x (pi) (up to sign) for i = 1, . . . , s − 1. We wish to identify ∂z ∂x (ps).
By assumption (ii), there exists a precursor pr to ps such that Hr and Hs intersect on a boundary Bz′ . Let vr = tz ∂z∂x (pr) be our estimate of ∂z ∂x (pr), for unknown sign tz ∈ {+1,−1}. Let vs be a unit normal vector to Hs, so that vs = ctz ∂z∂x (ps) for some unknown constant c. We pick the sign of vs so that it has the same orientation as vr with respect to the surfaceBz , and thus c > 0. Finally, let v = tz′ ∂z ′ ∂x (pr) = tz′ ∂z′ ∂x (ps) be our estimate of the gradient of z ′; where tz′ ∈ {+1,−1} is also an unknown sign (recall that since z′ is in layer k− 1 we know its gradient up to sign). We will use v and vr to identify vs.
Suppose that z = zkj is the jth neuron in layer k and that z ′ = zk−1h is the hth neuron in layer k− 1. Recall that
z(x) = zkj (x) = nk−1∑ i=1 Wkij ReLU(z k−1 i (x) + b k−1 i ). (3)
AsBz′ is the boundary between inputs for which z′ = zk−1h is active and inactive, ReLU(z k−1 h (x)+ bk−1h ) must equal zero either (Case 1) on Hr or (Case 2) on Hs.
In Case 1, we have ∂z
∂x (ps)−
∂z ∂x (pr) = W k hj
∂z′ ∂x (pr),
or equivalently: ctzvs − tzvr = Wkhjtz′v, which gives us the equation: cvs − vr = Wkhjtztz′v. Since we know the vectors vs,vr,v, we are able to deduce the constant c.
A similar equation arises in Case 2:
vr − cvs = Wkhjtztz′v, giving rise to the same value of c. We thus may complete our induction. In the process, observe that we have calculated a constant Wkhjtztz′t
′, where the sign t′ is +1 in Case 1 and −1 in Case 2. Note that tz′t′ can be calculated based on whether v points towards pr or ps. Therefore, we have obtained Wkhjtz , which is exactly the weight (up to z-dependent sign) that we wished to find. Once we have all weights incoming to z (up to sign), it is simple to identify the bias for this neuron (up to sign) by calculating the equation of any known local hyperplane for Bz and using the known weights and biases from earlier layers.
To complete the proof, we must now also calculate the correct signs tz′ of the neurons in layer k−1. Pick some z = zkj in layer k and observe that for all points ps ∈ Az there corresponds an equation, obtained by taking gradients in equation (3):
∂zkj ∂x (ps) = nk−1∑ i=1 Wkij1i,s ∂zk−1i ∂x (ps),
where 1i,s equals 1 if ps is on the active side of Bzk−1i . We can substitute in our (sign-unknown) values for these various quantities:
tzvs = nk−1∑ i=1 Wkij1i,stzk−1i vi.
Now, we may estimate 1i,s by a function 1′i,s that is 1 if ps and vi are on the same side of Bzk−1i . This estimate will be wrong exactly when tzk−1i = −1. Thus, 1i,s = (1 + tzk−1i 1 ′ i,s)/2, giving us the equation:
tzvs = nk−1∑ i=1 Wkij 1 + tzk−1i 1′i,s 2 tzk−1i vi
= 1
2 nk−1∑ i=1 Wkij(tzk−1i + 1′i,s)vi
All the terms of this equation are known, with the exception of tz and the nk−1 variables tzk−1i – giving us a linear system in nk−1 + 1 variables. For a given zkj , there are nk−1 different ps representing the intersections with Bz′ for each z′ in layer k − 1; choosing these ps should in general give linearly independent constraints. Moreover, the equation is in fact a vector equality with dimension nin; hence, it is a highly overconstrained system, enabling us to identify the signs tzk−1i for each zk−1i . This completes the proof of the theorem.

Review summaries:
This paper introduces an approach to recover weights of ReLU neural networks by querying the network with specifically constructed inputs. The authors notice that the decision regions of such networks are piece-wise linear corresponding to activations of individual neurons. This allows to identify hyperplanes that constitute the decision boundary and find intersection points of the decision boundaries corresponding to neurons at different layers of the network. However, weights can be recovered only up to permutations of neurons in each layer and up to a constant scaling factor for each layer.

This paper introduces a procedure for reconstructing the architecture and weights of deep ReLU network, given only the ability to query the network (observe network outputs for a sequence of inputs).  The algorithm takes advantage of the piecewise linearity of ReLU networks and an analysis by [Hanin and Rolnick, 2019b] of the boundaries between linear regions as bent hyperplanes.  The observation that a boundary bends only for other boundaries corresponding to neurons in earlier network layers leads to a recursive layer-by-layer procedure for recovering network parameters.  Experiments show ability to recover both random networks and networks trained for a memorization task.  The method is currently limited to ReLU networks and does not account for any parameter-sharing structure, such as that found in convolutional networks.