arXiv:2609.18682v1 [stat.ML] 16 Sep 2026
Rank and computation of the pathlifting Jacobian of a DAG ReLU network Manon Verbockhaven ∗ [email protected] ENS de Lyon, CNRS, Université Claude Bernard Lyon 1, Inria, LIP UMR 5668, 69342, Lyon cedex 07, France ✿
Abstract This paper provides a self-contained proof of the rank of the pathlifting Jacobian of a DAG ReLU network by performing an induction on the network’s number of hidden nodes. In fact, the induction is elementary, and the key recipe is to consider the skeleton matrix of the network, a sparse matrix encoding the network paths, and transform the representation of one of its hidden neurons into an output node. The proof relies on intermediate propositions which link the pathlifting, its Jacobian, the network parameters, and its skeleton matrix, which, on top of permitting to conclude on the rank of the pathlifting Jacobian, also provide a way to compute it without backpropagation and whose computation cost is super efficient in practice compare to usual backpropagation. The paper is provided with a Python module that implements the different propositions of the paper for feed forward networks and is used to experimentally quantifies the computational gain of computing the pathlifting Jacobian with the proposed theory.
1
Introduction
Most network architectures can be represented by Directed Acyclic Graph (DAG) ReLU networks, a generalized version of the feed-forward ReLU networks. The output of such a network is computed through the computation of its DAG, where each node is the application of the ReLU or the identity function, and each edge is a linear application whose coefficient is given by a parameter of the network. Compared to arbitrary computational graphs, DAG ReLU Networks are rather simple to study. This is partly due to the piecewise linearity of those network activation functions, which simplifies the network prediction and has permitted proofs on its approximation properties Hornik et al., Parhi and Nowak [2021], Lin et al. [2022], Leshno et al., its generalization and optimization properties Jacot et al. [2018], Chizat et al. [2019], on its Lipschitz constant Gonon et al. [2025], and on its intrinsic dynamics Marcotte et al. [2026]. Among the different tools that have brought to light the theoretical properties of DAG ReLU networks, we remark the pathlifting function Φ, a function mapping the network parameters to their vector of paths. The pathlifting is indeed a well-suited tool for the theoretical study of DAG ReLU networks because it locally linearises the network’s prediction function and is agnostic to the non-negative homogeneity of the ReLU activation. In particular, the pathlifting function has been used to establish generalization bounds Gonon et al. [2024], study the intrinsic dynamics of its pathlifting kernel matrix Marcotte et al. [2026], accelerate the network training Lebeurrier et al. [2026] and penalize the training criterion Parhi and Nowak [2021], Neyshabur et al.. Although the pathlifting function has been used in theory, it is rarely used in practice because its is a very high-dimensional vector. Generally, only some of its attributes are computed, for example, its dimension and its norm that can be computed in one forward pass Gonon [2024], Gonon et al. [2024], and the diagonal coefficient of ∗ Go to my web page.
its pathlifting kernel matrix ∂θ Φ⊤ ∂θ Φ that can be computed in one forward-backward pass Lebeurrier et al. [2026]. The focus of this paper is the Jacobian of the pathlifting function, ∂θ Φ, which has already been studied in Marcotte et al. [2026] through the dynamics of the pathlifting kernel matrix ∂θ Φ⊤ ∂θ Φ. An interesting result of this previous work, which we are able to recover in this paper with an independent methodology, is that for a DAG ReLU network with d parameters and h hidden neurons, the rank of its pathlifting Jacobian ∂θ Φ is equal to d − h. In the work of Marcotte et al. [2026] this theorem is proved by an equal upper and lower bound on the rank of the Jacobian matrix ∂θ Φ, where the upper bound is provided by a result of the paper (Corollary 3.4) and the lower bound (Appendix F) is obtained using a more general theorem from graph theory Gleiss et al. [2003]. In fact, this double bounds and the use of an external theorem to conclude on the rank of the Jacobian ∂θ Φ makes the proof pretty technical and convoluted. In our work, we take a different approach to determine the rank of the pathlifting Jacobian of a DAG ReLU network. We connect this Jacobian to the network’s skeleton matrix (a sparse matrix encoding the path of the network) and prove its rank by induction on the network number of hidden neurons. Compared to the work of Marcotte et al. [2026], our proof is elementary and mainly relies on a topological sort of the graph and some symmetries of the skeleton matrix. To prove the theorem on this Jacobian rank, we use intermediate propositions that rewrite the pathlifting and its Jacobian as a matrix product between the parameters, the pathlifting, and the skeleton matrix, which, on top of permitting to conclude on the rank of the pathlifting Jacobian, also provides an efficient way to compute the pathlifting Jacobian without backpropagation where the differentiations over the elements of the pathlifting vector are replaced by a cheaper matrix product. While some of those intermediate results were also used and proved in Marcotte et al. [2026], we provide new proofs based on first-order expansion and a Python implementation available at this GitLab. The paper is organized as follows. In the first section, we define the main objects of the paper and state the main propositions and the main theorem. In a second section, we provide a sketch of proof for the main theorem. In the last section, we quantify experimentally the gain of using the proposed theory to compute the pathlifting Jacobian compared to backpropagation. 1.1
General notations and objects
We note R(r) the r-dimensional real vector space and R(r1 , · · · , rq ) the (r1 , · · · , rq )-dimensional real vector space. Let f : R(d) 7→ R(q) be a function, when f is differentiable, we note ∂x f ∈ R(q, d) the jacobian matrix of f at x ∈ R(d) and when f is a real-valued function, we note ∇x f ∈ R(d) its gradient ⊤ vector with the convention that ∇x f = (∂x f ) . We represent a Directed Acyclic Graph (DAG) G by its list of nodes N = {n1 , · · · nm } and its list of oriented edges E = {e1 , · · · ed } with the property that there is no cycle in the graph. We define a DAG ReLU network F, a computational graph whose graph is a DAG where some nodes are designated as input and output nodes. This network is also characterized by its parameters θ ∈ R(d) and its prediction function noted fθ . For a given DAG ReLU network F, let P be the number of paths connecting one input to one output node in its DAG, we note Φ(θ) ∈ R(P ) the vector whose value at index p ∈ {1, · · · , P } is the product of the network weights along the path p. The dimensions of the main objects are summarized in the following table.
Symbol r, q θ Φ(θ) ∂θ Φ
Table 1: Objects dimensions. class Description N∗ number of input and output nodes R(d) Parameters of the network R(P ) Pathlifting of the network R(P, d) Jacobian of the pathlifting
2
2
Properties of the pathlifting and its Jacobian
In this section, we present the DAG ReLU network, the pathlifting function, and define the skeleton matrix. Then we connect those objects to one another through propositions. 2.1
Main definitions
We consider a DAG ReLU network F with vector of parameters θ ∈ R(d) and with DAG G described by its list of node N = {n1 , . . . , nm } and its list of oriented edges E = {e1 , . . . , ed }. The indexes of the edges in E are isomorphic to the index of θ and the prediction function of F, noted fθ : R(r) 7→ R(q), is defined as the results of the computational graph of G where each node represents the application of the ReLU max(0, ·) or the identity function, and each edge is the linear application whose coefficient is the parameter associated to it. The definition and the association of the network F with its DAG G allow us to distinguish three subsets of its nodes in N : the input nodes I, the output nodes O, and the hidden nodes H. The input nodes are associated with the network’s input and can be identified in the graph as the nodes with no incoming edges. The output nodes are associated with the network’s outputs and cannot be inferred from the graph representation and contains every node with no outgoing edge, together with any additional node designated as an output by the architecture. Finally, a node is a hidden node when it is neither an input nor an output node. Remark that those three subsets are a partition of N , i.e I ∩H =I ∩O =H ∩O =∅
and
I ∪H ∪O =N .
(1)
Remark 1. With this convention, the network’s biases are treated as input nodes, and their input values are set to 1. The pathlifting function Φ of a network is a function that maps its parameters θ to its vectors of paths, where a path is a set of edges that connects an input node to an output node in the graph. For a DAG ReLU network with DAG G, let P be the number of paths connecting one input node to one output node in the graph G then, the pathlifting function Φ : R(d) 7→ R(P ) is the function whose value at index j for j ∈ {1, · · · , P } equals the product of all the parameters along the path j. Strictly speaking, we defined the pathlifting function as follows. Definition 1. For DAG ReLU network with DAG G with edge list E isomorphic to the index of θ, let P be the number of paths in the network then, for j ∈ {1, . . . , P } a path index in the network, let e1 , . . . , edj be the list of edges crossed by the path j, then for θ ∈ R(d), we defined Φ(θ) at index j as : Φ(θ)j =
dj Y
θ ek
(2)
k=1
The main characteristic of the pathlifting function is that, for a finite-dimensional dataset, it locally linearises the network’s prediction function. While this proposition is well-known in the literature, we recal this property in the next proposition for the sake of completeness. Proposition 1. For a DAG ReLU network with parameters θ ∈ R(d) and prediction function fθ , let {xi }ni=1 ∈ R(r)⊗n be a dataset and µ a measure on θ, {xi }ni=1 that is absolutely continuous w.r.t. the Lebesgue measure, then µ− almost surely, there exists O a neighborhood of θ and L : R(P ) 7→ R(q)⊗n a linear application such that Proof:3 ∀θ′ ∈ O {fθ′ (xi )}ni=1 = L Φ(θ′ ) . (3) The the function L is provided in the proof of proposition 1 and is encoded in the Python module. For more details on the definition properties of the pathlifting function, we refer the reader to Chapter 2 of Gonon [2024]. 3
The last object we introduce is the skeleton matrix B of a network. The skeleton matrix of a DAG ReLU network is a sparse matrix encoding the absolute dependency of the network’s paths with respect to its parameters. Strictly speaking, we define the skeleton matrix as follows. Definition 2. Let F be a DAG ReLU network with d parameters and with P paths, we define B ∈ R(P, d), the skeleton matrix of F as the matrix whose coefficients are defined as follows. 1 if the ith path of F is dependent of the parameters θj Bij = (4) 0 otherwise To finish this subsection, we provide in fig. 1 an example of a DAG ReLU network with its pathlifting function and its skeleton matrix.
θ1 θ5 θ2 θ6 Φ(θ) = θ3 θ5 θ θ 4 6 θ7
1 0 B = 0 0 0
0 1 0 0 0
0 0 1 0 0
0 0 0 1 0
1 0 1 0 0
0 1 0 1 0
0 0 0 0 1
Figure 1: left: DAG of a feed-forward ReLU network with bias and one hidden layer. The nodes are represented with circles and the edges with black oriented arrows. The green (resp. red) arrows indicate the input (resp. the output) nodes, and the bias nodes are circled in dark blue. The nodes are indexed with letters, while the edges are indexed with integers. The node sets are: I = {a, c, g}, O = {h}, H = {d, f }. Middle: pathlifting function Φ of the network whose DAG is the left figure. Right: skeleton matrix B associated to Φ of the middle figure.
2.2
Propositions and theorem
We now present propositions that connect the pathlifting function, its Jacobian, and the skeleton matrix, and then present the main theorem on the rank of the pathlifting Jacobian. We note to the reader that some of the propositions were already known in the literature (Marcotte et al. [2026]), in particular proposition 2 and theorem 1. However, we provide a new proof of proposition 2 using a first-order Taylor expansion, and a new proof of theorem 1 by induction. Let µ be a measure on θ that is absolutely continuous with respect to the Lebesgue measure, the following equality holds. Lemma 1. Let | · |, exp and log be the entry-wise application of the associated function, and let S ∈ R(P, P ) be the diagonal matrix whose diagonal coefficients are the signs of Φ(θ), then µ almost surely Proof:4 Φ(θ) = S exp B log(|θ|) ∈ R(P ) . (5) This result is a key element that is to be be used to compute the pathlifting’s Jacobian using the skeleton matrix. Proposition 2. With diag the operator that maps a vector u to the diagonal matrix with diagonal entries given by u, then µ almost surely Proof:4 1 ∂θ Φ = diag(Φ)Bdiag( ) θ
(6)
where the dependence of ∂θ Φ and Φ in θ has been omitted for clarity and θ1 ∈ R(d) is the vector whose ith coordinate is equal to θ1i .
4
In fact, for both results, the µ almost surely statement excludes the ill-condition cases where θ has a null coordinate, which also corresponds to the point where the pathlifting Φ is not differentiable. We remark that proposition 2 provides an expression of the pathlifting Jacobian as a function of Φ and θ, and whose total computational complexity is O(dP ) as each element (i, j) of ∂θ Φ can be computed independently with Φi Bi,j θ1j . In fact, this asymptotic computational cost is similar to the one obtained when backpropagating each element of Φ; however, as shown in the experimental section of this paper, the matrix product in proposition 2 is naturally parallelizable and is super-efficient in practice compare to usual backpropagation. From proposition 2, one can deduce that the skeleton matrix B ∈ R(P, d) is equals to the jacobian of Φ at point θ = 1d ∈ R(d) the vector full of ones. This property was also used in Marcotte et al. [2026] and is stated in the following corollary. Corollary 1. Let d be the dimension of the parameter θ and 1d ∈ R(d) be the vector full of ones, then B = ∂θ Φ(1d ) .
(7)
From proposition 2, one can easily deduce an equality on the rank of the pathlifting Jacobian. Corollary 2. µ almost surely, the rank of the jacobians of Φ equals to the rank of its skeleton matrix, i.e. µ almost surely Proof:4 rk(∂θ Φ) = rk(B) .
(8)
We conclude this section with the main theorem that is provided with a sketch of proof in section 3. For F be a neural network with input set I, output set O, hidden node set H, and skeleton matrix B, then the following result holds. Theorem 1. Note # the cardinality operator, the rank of the skeleton matrix of F is Proof:2 rk(B) = #E − #H .
(9)
Corollary 2 and theorem 1 leads to the following corollary, which concludes the section. Let F be a neural network with parameter θ, the following result holds. Corollary 3. Let d be the dimension of the parameter of F and h the number of hidden nodes in F then, µ almost surely rk(∂θ Φ) = d − h .
3
(10)
Sketch of proof
In this section, we provide a sketch of proof for theorem 1. To mimic the induction of the general proof, we chose two simple DAG ReLU networks on which we apply the general proof. The first network is chosen with no hidden nodes to illustrate the initialization of the induction, and the second network is chosen with one hidden node to illustrate one step of the induction. 3.1
Initialization of the induction
We consider a DAG ReLU network with no hidden nodes, h = 0, and whose DAG is given in fig. 2. Its pathlifting function Φ and skeleton matrix B are defined in eq. (11). The columns of the skeleton matrix B are ordered according to the list of edges indicated at its top, and its rows are ordered to match the pathlifting function indexing.
5
1 1 θ1 0 θ2 Φ(θ) = θ2 θ5 , B = 0 0 θ 3 0 θ4 0 θ4 θ5
Figure 2: DAG of a network with no hidden node, the green and the red arrows represent the input nodes and the output nodes, respectively. The nodes are indexed with letters N = {a, b, c, d} and the edges with integers E = {1, 2, 3, 4, 5}.
2 0 1 1 0 0 0
3 0 0 0 1 0 0
4 0 0 0 0 1 1
5 0 0 1 (11) 0 0 1
To compute the rank of B, we apply invertible row operations on it, then evaluate the rank of the resulting matrix. Indeed, performing row operations on a matrix is equivalent to applying invertible matrices to its left side; thus, the rank is not changed. We choose the row operations that take advantage of some specific properties of the skeleton matrix B and which are embodied by the following lemma. Lemma 2. For a DAG ReLU network with no hidden nodes, for all l ≥ 2, for all path p of length l, let e1 , . . . el be the ordered list of edges crossed by path p, then it exists a path p̃ of size l − 1 that goes through the list of edges e1 , . . . , el−1 , as a consequence Proof:5 B[p, :] − B[p̃, :] = (0
·
0
1
0
·
0)
(12)
where the only non-null element is at the index associated with the edge el , the last edge crossed by path p. This lemma can be easily checked on the fig. 2: the only paths of length greater than one are the third and sixth path of Φ, they respectively go across the list of edges 2, 5 and 4, 5 and indeed the second path of Φ is of length one and goes through 2 and the fifth path of Φ is of length one and goes through 4. Using this symmetry, we construct the algorithm algorithm 1, which takes as input the matrix B and outputs a matrix B̃ of the same rank as B. Data: B the skeleton matrix, lmax the maximum length of a path Result: matrix B̃ of the same rank as B for l = lmax , lmax − 1, . . . , 2 do for p of length l do let p̃ be the path defined in lemma 2 for path p; B[p, :] ← − B[p, :] − B[p̃, :]; end end Algorithm 1: Row operations on matrix B
1 0 0 B̃ = 0 0 0
0 1 0 0 0 0
0 0 0 1 0 0
0 0 0 0 1 0
0 0 1 (13) 0 0 1
Let B̃ be the matrix outputted by algorithm 1 and provided in eq. (13), then, because of lemma 2, each of its rows has only one non-null element thus its rank is equal to the number of its non-null columns, which is equal to 5, which is also the dimension of θ. It follows that
rk(B) = rk(B̃) = 5 = d − 0 . 6
(14)
3.2
One induction step
We now suppose that the theorem is true for any DAG ReLU network without hidden nodes and perform one step of induction. We choose a network F with one hidden node h = 1 and whose representation is given in fig. 3. Its pathlifting Φ and its skeleton matrix B are described in eqs. (15) and (16).
θ1 θ2 θ θ Φ(θ) = 2 6 θ3 θ4 θ3 θ5 θ3 θ5 θ6 Figure 3: DAG of a network with one hidden node, the 1 green and the red arrows represent the input nodes and 0 the output nodes, respectively. The nodes are indexed 0 with letters and the edges with integers. The set of B = 0 u u k edges E− = {3}, E+ = {4} and E− = {2} are colored 0 in dark yellow, purple and cyan. The blue edge 5 is the 0 edge connecting the hidden node u to the output node k.
0 1 1 0 0 0
0 0 0 1 1 1
0 0 0 1 0 0
(15)
0 0 0 0 1 1
0 0 1 (16) 0 0 1
For this part of the sketch, we need a topological sort of the network’s nodes, which we choose as the list {a, b, u, k, f }. The key idea of the induction is to transform the last hidden node of the topological sort (node u), into an output node and then use the induction hypothesis. In fact, this goal is achievable because the column of the skeleton matrix associated to the edge 5 connecting node u and node k is linearly dependent on the columns associated with the incomming and outcomming edges of node u. We perform this operation in two steps, which is one extra step compared to the induction initialization. In a first step, we permute the columns and the rows of B to uncover its structure then, we perform column and row operations on it. step 1 : re-ordering We consider u the unique hidden node of the network and identify the next node in the topological sort that is connected to it: node k. Then, we defined four types of edges in the graph, which can be visualized with different colors in fig. 3. The edge 5, that make the connection between node u and node k; the out-going u u edges of u except 5 noted E+ ; the incomming edges of node u noted E− ; and the in-going k edges of node k except 5 noted E− . We have u E+ = {4}
u E− = {3}
k E− = {2} .
Then, we rearrange the columns of B such that its first column is associated to the edge 5, u u the second column is associated to the edge in E+ , the thrid column to the edge in E− , the k fourth column to the edges in E− and then the rest of the edges. We save the result of this permutation in the matrix B ′ whose columns are now ordered with respect to the list of edges {5, 4, 3, 2, 1, 6}. The rank of matrix B ′ is equal to the rank of matrix B.
7
u u k E+ E− E− 5 4 3 2 1 0 0 0 0 1 0 0 0 1 0 B′ = 0 0 0 1 0 0 1 1 0 0 1 0 1 0 0 1 0 1 0 0
6
0 0 1 0 0 1
Φ(θ)5 B ′′ = Φ(θ)6 Φ(θ)4 Φ(θ)2 Φ(θ)3 Φ(θ)1
(17)
u u k E+ E− E− 5 4 3 2 1 1 0 1 0 0 1 0 1 0 0 0 1 1 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 1
6 0 1 (18) 0 0 1 0
Then, we permute the rows of B ′ by grouping on top the paths crossing both node u and node k : {Φ(θ)5 , Φ(θ)6 }, then all the paths crossing only node u : {Φ(θ)4 }, then all the paths crossing only node k : {Φ(θ)2 , Φ(θ)3 } and then all the remaining ones :{Φ(θ)1 }. We save the result of this permutation in the matrix B ′′ whose rows are now ordered with respect to the list of paths {Φ(θ)5 , Φ(θ)6 , Φ(θ)4 , Φ(θ)2 , Φ(θ)3 , Φ(θ)1 }. The rank of matrix B ′′ is still equal to rank of matrix B. With the writing of B ′′ , the structure of the initial matrix B is revealed with the blue, the green, and the purple zeros, which are proved in the main proof to be the result of the performed row and column re-ordering.
step 2: column and row operations We now perform two operations on the columns of B ′′ . First, we use the columns associated u with the edge in E− that is full of ones on its top and full of zeros on its bottom (a property that is proved in the main proof as a direct consequence of the previous permutations). We u subtract this column to the first column of B ′′ . Then, we take the column of E+ , i.e., the second column, and we add it to the first column. The resulting matrix B̃ is of the same rank as B and is equal to
Φ(θ)5 B̃ = Φ(θ)6 Φ(θ)4 Φ(θ)2 Φ(θ)3 Φ(θ)1
5 0 0 0 0 0 0
u u k E+ E− E− 4 3 2 1
6
0 0 1 0 0 0
0 1 . 0 0 1 0
1 1 1 0 0 0
0 0 0 1 1 0
0 0 0 0 0 1
(19)
We remark that the column associated to the edge 5 is full of zeros, thus the obtained matrix B̃ get closer to the skeleton matrix of a network whose graph is the same of F but without edge 5. In fact, we are one step away from this affirmation as we still need to remove the 1 associated to the paths that were crossing the edge 5 but not ending at node k. Indeed, remark that the second row on B̃, and which was previously associated to Φ(θ)6 , does not correspond to a path anymore and one should remove either its dependency on 6 or its dependency in 3. To do so, we perform row operations on B̃ using some symmetries of B̃ which are similar to those used in the initialization. Lemma 3. Consider a graph whose node indices are ordered with a topological sort, and let k an output node such that for all k ′ > k node k ′ is an output node, then, for any p of length l ≥ 2 if p crosses node k and not ending at k it exists a path p̃ of size l − 1 that coincide with p on its l − 1 first nodes. As a consequence : Proof:8 B̃[p, :] − B̃[p̃, :] = (0
·
0
1
0
·
0)
where the only non-null element corresponds to the last edge crossed by path p.
8
(20)
Once again, this lemma can be easily verified here. The paths crossing node k and not ending at k are the path Φ(θ)3 = θ2 θ6 which coincides with Φ(θ)2 = θ2 and the path Φ(θ)6 = θ3 θ5 θ6 which coincides with Φ(θ)5 = θ3 θ5 . We now use the following algorithm to take advantage of lemma 3. Data: B̃ the modified skeleton matrix, P the list of path crossing node k and not ending at node k, lmin , lmax the minimum and maximum length of a path in P. Result: matrix B̃ ′ of the same rank as B̃ for l ∈ {lmax , lmax − 1, · · · , lmin } do for p ∈ P and p of length l do Let p̃ be the path of lemma 3 coinciding with p on its l − 1 first nodes. B̃[p, :] ← B̃[p, :] − B̃[p̃, :] end end Algorithm 2: Row operations on matrix B̃
u u k E+ E− E− 5 4 3 2 1 0 0 1 0 0 0 0 0 0 0 B̃ ′ = 0 1 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1
6 0 1 (21) 0 0 1 0
For our specific case, this algorithm subtracts the row associated with Φ(θ)2 from the row associated with Φ(θ)3 and the row associated with Φ(θ)5 from the row associated with Φ(θ)6 . We obtain the matrix B̃ ′ that is of the same rank as B and is given in eq. (21). With the matrix B̃ ′ , for any edges connecting two output nodes and which were previously on a paths crossing node u (here the edge 6), it exists a line in B̃ ′ with only one no-null element on its row associated to that edge index (line 2 and 5). We use these rows, for example the second line of B̃ ′ , to remove all the dependency of the edge 6 in the other lines of B̃ ′ . This operation is done by subtracting the second line of B̃ ′ from the fifth line of B̃ ′ . We save the result of this operation in the matrix B̃ ′′ , which is still of the same rank as B and is provided in eq. (22).
5 0 0 B̃ ′′ = 0 0 0 0
4 0 0 1 0 0 0
3 1 0 1 0 0 0
2 0 0 0 1 0 0
16 θ3 0 0 0 1 θ θ 3 4 0 0 , Φ = (22) θ2 0 0 0 0 θ1 1 0
Figure 4: DAG of a network with no hidden node associated with the pathlifting function and skeleton matrix of eq. (22).
When removing the columns associated with edge 6 in B̃ ′′ , we remark that the resulting matrix is associated with a DAG ReLU network whose graph is the same as F but without the edges 5 and 6 and where the node u has been transformed into an output node. The pathlifting and DAG associated with such a graph are provided in eq. (22) and fig. 4. Let F be the skeleton matrix of the DAG ReLU network of fig. 4, then, because we have emptied the second row and last column of B̃ ′′ , we have rk(B̃ ′′ ) = rk(F ) + 1, by induction rk(F ) = d − 2, it follows that rk(B) = rk(B̃ ′′ ) = rk(F ) + 1 = d − 2 + 1 = d − h which concludes the sketch. 9
(23)
4
Experiment
In this last section of the paper, we use the Python package available at this GitLab to compare the computational cost of computing ∂θ Φ(θ) ∈ R(P, d) when such computation is done using proposition 2 or by backpropagation with the Python package torch. We provided the details on the experiment and the pseudo code for the computation of the pathlifting Φ(θ) and the skeleton matrix B for an arbitrary feed-forward network in section B. We consider a feed forward ReLU network fθ : R(r) 7→ R(q) with L hidden layers and where each hidden layer l has wl hidden nodes. We denote d the dimension of the network parameters θ and P the dimension of the pathlifting vector Φ(θ). We consider two methods to compute the Jacobian ∂θ Φ(θ). ✿ The method using the skeleton matrix with ∂θ Φ(θ) = diag(Φ(θ))Bdiag( θ1 ) of proposition 2. ✿ The method using PyTorch automatic differentiation Paszke et al. [2017] at each index of Φ(θ). The implementation of those two methods are provided in algorithms 4 and 7. In the left figure fig. 5, we plot the time in seconds to compute the pathlifting Jacobian using the two described methods. This computational time is displayed as a function of the variable P d, which is obtained by taking L ∈ J1, 3K and wl is constant through the hidden layers and equal to w ∈ J1, 8K. Each setting is evaluated 5 times, and we plot the mean as a solid line and the standard deviation as a transparent line. As expected, computing the Jacobian with the skeleton matrix is faster than using the naive method, which loops over the dimensions of the pathlifting. To fairly compare the two methods, and because algorithm 7 uses the skeleton matrix as an additional input, we also plot the time complexity of computing the skeleton matrix (algorithm 12) at the bottom of fig. 5. We see that such computational cost grows with the number of paths; however, such cost can easily be neglected because the skeleton matrix does not depend on θ and can be computed once and for all at the network initialization and reused for the different computations of ∂θ Φ(θ). Remark 2. This computational gain holds when the manipulated tensors Φ(θ) and B can be stored in memory. However, for theoretical study with relatively small networks, the gain in time is huge.
Compute of B in seconds
Compute of in seconds
150
Skeleton Autograd
100
Data: θ the current parameters.ϕ := the pathlifting at point θ, B the skeleton matrix Result: J the Jacobian of ϕ at θ u ← θ1 ; J = torch.einsum(′ P, P d, d− > P d ′ , ϕ, B, u); Algorithm 3: Jacobian of Φ(θ) with B
50 0
0
50000 100000 150000
0.03
Data: θ the current parameters.ϕ := the pathlifting at point θ, Result: J the Jacobian of ϕ at θ 0.01 J = zeros(P, d); for i ∈ [P ] do 0.00 J[i, :] = 0 50000 100000 150000 torch.autograd.grad(ϕi , θ, #PARAMS * #PATHS retain graph = T rue); end Figure 5: Times in seconds to compute the Jacobian matrix ∂θ Φ(θ) and the skeleton matrix B using al- Algorithm 4: Jacobian of Φ(θ) with augorithms 4 and 7 as a function of the variable P d. tograd [ r = 5, q = 2]
0.02
10
5
Conclusion
We hope this paper has helped the reader to grasp the key element of the induction and the structure of the pathlifting Jacobian of a DAG ReLU network. The computation of pathlifting and its Jacobian remains an issue for large networks; however, the provided module is a useful tool for testing conjectures and manipulating the pathlifting and its Jacobian on toy networks.
Acknowledgement I gratefully acknowledge my supervisor Rémi Gribonval for his guidance during this work. I gratefully acknowledge the support of the Centre Blaise Pascal’s IT test platform at ENS de Lyon (Lyon, France) for Machine Learning facilities. The platform operates the SIDUS solution Quemener and Corvellec [2013] developed by Emmanuel Quemener. This work was supported in part by the AllegroAssai ANR19-CHIA-0009 project of the French Agence Nationale de la Recherche (ANR) and by the SHARP ANR project ANR-23PEIA-0008 in the context of the France 2030 program.
References Lénaı̈c Chizat, Edouard Oyallon, and Francis Bach. On Lazy Training in Differentiable Programming. In Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019. Petra Gleiss, Josef Leydold, and Peter Stadler. Circuit bases of strongly connected digraphs. Discussiones Mathematicae Graph Theory, 23(2):241–260, 2003. Antoine Gonon. Harnessing symmetries for modern deep learning challenges : a path-lifting perspective. Theses, Ecole normale supérieure de lyon - ENS LYON, November 2024. URL https://theses.hal.science/tel-04784426. Antoine Gonon, Nicolas Brisebarre, Elisa Riccietti, and Rémi Gribonval. A path-norm toolkit for modern networks: consequences, promises and challenges. In The Twelfth International Conference on Learning Representations, 2024. URL https://openreview.net/forum?id= hiHZVUIYik. Antoine Gonon, Nicolas Brisebarre, Elisa Riccietti, and Rémi Gribonval. A rescaling-invariant lipschitz bound based on path-metrics for modern reLU network parameterizations. In Forty-second International Conference on Machine Learning, 2025. URL https://openreview.net/ forum?id=T8VLY1KuOz. Kurt Hornik, Maxwell Stinchcombe, and Halbert White. Multilayer feedforward networks are universal approximators. 2(5):359–366. ISSN 0893-6080. doi: 10.1016/0893-6080(89)90020-8. URL https://www.sciencedirect.com/science/article/pii/0893608089900208. Arthur Jacot, Franck Gabriel, and Clement Hongler. Neural tangent kernel: Convergence and generalization in neural networks. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. CesaBianchi, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018. Arthur Lebeurrier, Titouan Vayer, and Rémi Gribonval. Path-conditioned training: a principled way to rescale relu neural networks, 2026. URL https://arxiv.org/abs/2602.19799. Moshe Leshno, Vladimir Ya. Lin, Allan Pinkus, and Shimon Schocken. Multilayer feedforward networks with a nonpolynomial activation function can approximate any function. 6(6):861– 867. ISSN 08936080. doi: 10.1016/S0893-6080(05)80131-5. URL https://linkinghub. elsevier.com/retrieve/pii/S0893608005801315. Ting Lin, Zuowei Shen, and Qianxiao Li. On the Universal Approximation Property of Deep Fully Convolutional Neural Networks. September 2022. 11
Sibylle Marcotte, Gabriel Peyré, and Rémi Gribonval. Intrinsic training dynamics of deep neural networks. In The Fourteenth International Conference on Learning Representations, 2026. URL https://openreview.net/forum?id=IlyesljaNb. Behnam Neyshabur, Russ R Salakhutdinov, and Nati Srebro. Path-SGD: Path-Normalized Optimization in Deep Neural Networks. In Advances in Neural Information Processing Systems, volume 28. Curran Associates, Inc. URL https://proceedings.neurips.cc/paper/2015/ hash/eaa32c96f620053cf442ad32258076b9-Abstract.html. Rahul Parhi and Robert D. Nowak. Banach Space Representer Theorems for Neural Networks and Ridge Splines, February 2021. Adam Paszke, Sam Gross, Soumith Chintala, Gregory Chanan, Edward Yang, Zachary DeVito, Zeming Lin, Alban Desmaison, Luca Antiga, and Adam Lerer. Automatic differentiation in PyTorch. October 2017. Emmanuel Quemener and Marianne Corvellec. Sidus—the solution for extreme deduplication of an operating system. Linux J., 2013(235), November 2013. ISSN 1075-3583.
12
A
Proofs Proposition 3. For a DAG ReLU network with parameters θ ∈ R(d) and prediction function fθ , let {xi }ni=1 ∈ R(r)⊗n be a dataset and µ a measure on θ, {xi }ni=1 that is absolutely continuous w.r.t. the Lebesgue measure, then µ− almost surely, there exists O a neighborhood of θ and L : R(P ) 7→ R(q)⊗n a linear application such that Proof:3 ∀θ′ ∈ O {fθ′ (xi )}ni=1 = L Φ(θ′ ) . (24)
Proof. Let {xi }ni=1 ∈ R(r)⊗n be a finite dataset and let µ be a measure on the network parameters θ and {xi }ni=1 that is absolutely continuous with respect to the Lebesgue measure. We restrict our proof to the networks whose output nodes are associated with the identity activation function. This is not restrictive, as any DAG ReLU network can be mapped to such a network. Without loss of generality, we suppose that the input nodes associated with the biases have been xi concatenated to the input, i.e xi ← ∈ R(r). 1 To construct the appropriate linear function L , we first construct a neighborhood O of θ on which the activation pattern of the network is constant, and then construct the appropriate linear function. Construction of the neighborhood O. Let θ ∈ R(d) be a parameter initialization and let A(θ, x) ∈ R(s) be the pre-activation of the network at point x with parameter θ. For any x ∈ R(r), the function A(·, x) is continous, and for any θ each component of A(θ, ·) is a piecewise polynomial function. For a fixed θ with no null coordinates, each function index of A(θ, ·) is piecewise polynomial, and the number of regions on which it is polynomial is countable. Because the set of roots of a non zero polynomial function is a hyperplane of null Lebesgue measure, the roots of one function index of A(θ, ·) are included in a countable set of hyperplanes which is of null Lebesgue measure. As a consequence, the measure of the event {∃j, i such that a pre-activation has one null coordinate} is less than the measure of the union of a countable set of hyperplanes, which is null. It follows that Z n µ (θ, {xi }i=1 ) | ∃j, i A(θ, xi )j = 0 = µ {xi }i=1 | ∃j, i A(θ, xi )j = 0 dµ1 (θ) θ
with µ1 the marginal of µ on θ. The function in the integral is null µ1 −almost surely (for θ with no null coordinates), as a consequence the integral is null and the event of interest is of null Lebesgue measure. Thus, without loss of generality, we suppose that for all i ∈ {1, ..., n} the activation pattern of the network at point xi noted A(θ, xi ) has no null coordinates, this event being of null Lebesgue measure. Because A(·, xi ) is continuous and A(θ, xi ) has no null coordinates for all i, let ϵ such that for any i and θ′ ∈ Bθ (ϵ), the ball centered at θ and of radius ϵ, the activation pattern A(θ′ , xi ) has no null coordinates. We set O := Bθ (ϵ) a neighborhood of θ. Because A(·, x) is continuous, the activation pattern of the network at point xi is constant on θ′ ∈ O, and we denote it F = [act(A(θ, xi )), · · · , act(A(θ, xn ))] ∈ R(n, s), where act is the element-wise application of the positive part function at index j when the assoaciated activation function is ReLU and 1 otherwise.
Construction of the linear function L . Each path of the network connects one input node to one output node and is active at point xi if and only if all the index of the ith columns of F , i.e.
13
act(A(θ, xi )), associated to that path are equal to one. Those indexes are also the ones of the nodes crossed by the path. For p a path, let jxp be the input node index of p and jyp be the output node index of p. Let Jp be the set of indices of the hidden nodes crossed by the path p, each of them associated with an index in A(θ, xi )jy . We define Y cip = F [i, j] (25) j∈Jp
the product of all the activity patterns of the nodes crossed by path p for point xi . The coefficient cip is constant for θ′ ∈ O and indicates if the path is active at point xi . For θ′ ∈ O, let Φ(θ′ ) ∈ R(P ) be the vector of paths at parameter θ′ , and let j ∈ {1, · · · , q} be an output index. It follows that fθ′ (xi )j =
P X
Φ(θ′ )p cip 1j=jyp xi [jxp ]
(26)
p=1
where 1j=jyp is the indicator function that is equal to 1 if j = jyp and 0 otherwise. i c1 1j=jy1 xi [jx1 ] .. Let Cij := ∈ R(P ) and let L be the linear function defined by . ciP 1j=jyP xi [jxP ] 1 Ci , u ∀u ∈ R(P ), L (u) = ... . i=1,··· ,n q ⟨Ci , u⟩
(27)
It follows that for any θ′ ∈ O, we have {fθ′ (xi )}ni=1 = L Φ(θ′ ) .
(28)
Lemma 4. Let | · |, exp and log be the entry-wise application of the associated function, and let S ∈ R(P, P ) be the diagonal matrix whose diagonal coefficients are the signs of Φ(θ), then µ almost surely Proof:4 Φ(θ) = S exp B log(|θ|) ∈ R(P ) . (29)
Proof. Let F be a DAG ReLU network, and let B ∈ R(P, d) its skeleton matrix and Φ(θ) its vector of paths. Let θ ∈ R(d) be a parameter initialization and without loss of generality, we suppose that θ has no null parameters (this event being of null Lebesgue measure). Let S = diag(sign(Φ(θ))) ∈ R(P, P ) the diagonal matrix with coefficients Sii = sign(Φ(θ)i ).
14
To prove lemma 4, we shall prove the equality at each index of Φ(θ). Let j ∈ {1, ..., P }, we have P X S exp B log(|θ|) = Sji exp B log(|θ|) j
i,1
i=1
= Sjj exp B log(|θ|)
j,1
= sign Φ(θ)j exp
X d
Bjk log(|θk |) .
k=1
The sum on k ranges through all the parameters of the networks and the coefficient Bjk is equal to 1 iff the parameter k is in the expression of the path j. It follows that d X
Bjk log (|θk |) = log |Φ(θ)j |
(30)
k=1
and
S exp(B log(|θ|)) = sign Φ(θ)j |Φ(θ)j | = Φ(θ)j . j
Proposition 4. With diag the operator that maps a vector u to the diagonal matrix with diagonal entries given by u, then µ almost surely Proof:4 1 ∂θ Φ = diag(Φ)Bdiag( ) θ
(31)
where the dependence of ∂θ Φ and Φ in θ has been omitted for clarity and θ1 ∈ R(d) is the vector whose ith coordinate is equal to θ1i .
Proof. We prove the proposition by performing a first-order Taylor development of Φ on θ on a neighborhood V. Let θ ∈ R(d) be a parameter that has no null coordinates, and let V be a neighborhood of θ such that for all θ′ ∈ V, θ′ has no null coordinates. First order Taylor development of Φ on V. We use the row of the skeleton matrix B = T (B1 , ..., BP ) where Bj ∈ R(P ). Let h ∈ R(d) such that θ + h ∈ V, starting from the expression of Φ provided lemma 4, we have Φ(θ + h)j = S exp B log(|θ + h|) (32) j
= Sj,j exp Bj log(|θ + h|) 1 h|) = Sj,j exp Bj log(|θ|) + Bj log(|1d + diag θ
15
(33) (34)
h1 θ1
where 1d ∈ R(d) is the vector full of ones and diag( θ1 )h = . . We remark that, because hd θd
θ + h ∈ V we have for k = 1, ..., d, 0 < |hk | < |θk | < 1 and thus 0<1+
hk . θk
(35)
It follows that |1d + diag( θ1 )h| = 1d + diag( θ1 )h; thus, we can remove the absolute value in the exponential of eq. (34). We continue the Taylor development from eq. (34). 1 Φ(θ + h)j = Sj,j exp Bj log(|θ|) + Bj diag( )h + o(||h||) θ 1 = Sj,j exp (Bj log(|θ|)) exp Bj diag( )h + o(||h||) θ 1 = Sj,j exp Bj log(|θ|) 1 + Bj diag( )h + o(||h||) . θ Using again lemma 4, i.e Sj,j exp (Bj log(|θ|)) = Φ(θ)j , it follows that 1 Φ(θ + h)j = Φ(θ)j + Φ(θ)j Bj diag( )h + o(||h||) . θ By of the linear term in h, it follows that the j th row of ∂θ Φ is equal to identification ∂θ Φ j = Φ(θ)j Bj diag( θ1 ) ∈ R(1, d) and thus 1 ∂θ Φ = diag(Φ)Bdiag( ) . θ
Corollary 4. µ almost surely, the rank of the jacobians of Φ equals to the rank of its skeleton matrix, i.e. µ almost surely Proof:4 rk(∂θ Φ) = rk(B) .
(36)
Proof. For µ a measure on θ ∈ R(d), using proposition 4 we have µ almost surely : 1 ∂Φ = diag(Φ)Bdiag( ) θ As all the coordinates of θ are different from 0 µ− almost surely, thus µ− almost surely the matrix diag( θ1 ) and diag (Φ) are invertible and we have rk(∂θ Φ) = rk(B).
Theorem 2. Note # the cardinality operator, the rank of the skeleton matrix of F is Proof:2 rk(B) = #E − #H .
(37)
We prove theorem 1 by induction on the number of hidden neurons in the graph G of the network F which we denote by h = #H. Proof. Let F be a neural network with h hidden nodes and let G be its DAG. Let N = {n1 , · · · , nm } be its set of nodes, E = {e1 , · · · , ed } its set of edges, and B its skeleton matrix.
16
h = 0 : An example of such a graph is shown in fig. 6. The nodes are indexed with integers and the edges with letters. To compute the rank of the skeleton matrix B of this network, we apply invertible row operations on it, then evaluate the rank of the resulting matrix. Indeed, performing row operations on a matrix is equivalent to applying invertible matrices on its left side, and the resulting matrix after such operations is of the same Figure 6: Example of a DAG of a network withrank as the original matrix. We out a hidden node: the green and the red arrows choose the row operations that represent the input nodes and the output nodes, take advantage of some specific respectively. The nodes are indexed with letters properties of the skeleton matrix N = {na , nb , nc , nd , nf } and the edges with inB and which are embodied by the tegers E = {e1 , e2 , e3 , e4 , e5 , e6 , e7 , e8 , e9 }. following lemma.
Lemma 5. For a DAG ReLU network with no hidden nodes, for all l ≥ 2, for all path p of length l, let e1 , . . . el be the ordered list of edges crossed by path p, then it exists a path p̃ of size l − 1 that goes through the list of edges e1 , . . . , el−1 , as a consequence Proof:5 B[p, :] − B[p̃, :] = (0
·
0
1
0
·
0)
(38)
where the only non-null element is at the index associated with the edge el , the last edge crossed by path p.
Proof. Let l > 1 and p of length l going through the ordered list of edges e1 , . . . , el . Because the graph is a-cyclic and has no hidden node, the edge e1 connects an input node to an output node, and for all j = 2, . . . , l the edge ej connects two output nodes. As a consequence, the edge el−1 is directed to an output node and thus the path going through the edges e1 , ..., el−1 ending at el−1 exists. Using this symmetry, we construct the algorithm algorithm 5 which takes as input the matrix B and outputs a matrix B̃ that is of the same rank as B. Data: B the skeleton matrix, lmax the maximum path length in G Result: matrix B̃ of the same rank as B for l = lmax , lmax − 1, . . . , 2 do for p of length l do let p̃ be the path defined in lemma 5 for path p; B[p, :] ← − B[p, :] − B[p̃, :]; end end Algorithm 5: Row operations on matrix B The matrix B̃ outputted by algorithm 5 is of the same rank as B and each of its rows has a unique non-null element corresponding to the last edge crossed by the paths associated with that row (lemma 5). As a consequence the rank of B̃ is equal to number of its non-null columns.
17
As all the edges of the networks are directed toward an output, every edges are a last edge of one path, thus there is no null-columns in B̃ thus, the rank of B̃ equals the the number of columns, that is the number of parameters in the network. It follows that rk(B) = rk(B̃) = d − 0 .
Induction : We suppose theorem 2 is true for any DAG ReLU network with at most h − 1 hidden nodes. Let F be a DAG ReLU network with h hidden nodes. We note {n1 , . . . , nm } and {e1 , . . . , ed } the lists of its nodes and edges. Because there is no cycle in the graph of F, we index its nodes with a topological sort of its graph with the constraint that the input nodes are indexed first. We choose u as the larger hidden node index in the topological sort of the graph and let k > u be the smaller integer such that node nk is connected to node nu . Let e↔ be the edge connecting node nu and node nk . The key element of the proof is to remove the edge e↔ from the graph of F and transform nu into an output node. Those actions would remove one hidden node in the graph of F and would allow the use of the induction hypothesis. The technique of the proof mainly relies on the fact that the Figure 7: DAG of a network with h u column on the skeleton matrix at edge e↔ is hidden nodes. The set of edges E− , linearly dependent on the columns associated u k E+ and E− are colored in dark yelwith the incoming and outgoing edges of node low, purple and cyan. The blue u. edge e↔ is the edge connecting the The steps of the proofs are similar to the sketch hidden node nu to the output node in section 3. First, we re-order the columns and nk . row of the skeleton matrix, then we remove the edge e↔ , and finally we transform nu into an output node. In the sketch, those two last steps are done simultaneously. 1. Removing the edge e↔ u u Note E− the set of the in-going edges of nu and E+ the set of the outgoing edges of nu but ↔ k without e and E− the set of in-going edges of the nodes nk but without e↔ . Those different sets are indicated with color in fig. 7. We now present the symmetries of B with the following lemmas : u Lemma 6. If path p goes through node nu then p passes by a unique edge of E− and a u unique edge of {e↔ } ∪ E+ .
u u Proof. By definition, E− is the set of all the incoming edges of nu , and {e↔ } ∪ E+ is the set of all the outgoing edges of node nu , which concludes the proof.
Lemma 7. Let p be a path of F, then p can not simultaneously go through an edge of u u k E− ∪ E+ ∪ {e↔ } and an edge of E− .
18
Proof. reductio ad absurdum. u u We suppose that it exists a path p, such that p go through an edge of E− ∪ E+ ∪ {e↔ } k and through an edge of E− . Let p be such path. By construction p goes through node u and node k. Because p goes k through an edge in E− and because G has no cycle then path p does not cross the edge ↔ e . As a consequence, the path p crosses one intermediate node between nu and nk . Let nu , nα , ..., nk be the ordered list of nodes associated to sub path of p starting at nu and ending at nk . Because we have indexed the node using the topological sort, we have u < α < k. On the other hand, k is the smaller integer for which nk is connected to node nu , so k ≤ α, absurd.
We now re-order the columns of B such that it first rows correspond to u u k e↔ , E+ , E− and E− . We also reorder its lines so that the first lines correspond to all the paths crossing both nodes nu and nk , then all the paths crossing nu but not by node nk . The skeleton matrix is of the form of the right figure, where the blue zeros are induced by lemma 6, the magenta zeros are induced by lemma 7, and the green zeros are induced by lemma 7. The colored dots correspond to a repetition of 0 in the matrix.
e↔ 1 .. . 1 0 . . . B= 0 · 0 . .. 0 0
u E+ ... 0 . .. . .. ... 0 ... 0 . .. . .. ... 0 .. . · · ... 0 1 .. .. .. . . . ... 0 1 0 0 0
0 .. . 0 1 .. . 1
u E−
k E−
.
A1
0
M1
A2
0
M2
.. .
.. .
·
A−1
0
M−1
0
D
·
u Furthermore, as a path crosses at most one edge of E− ( lemma 6), the matrices indexed on letter A are of the same form as the first block matrix of B with only one non-null element by row as 1 0 · · .. .. . . · · 1 0 · · 0 1 0 · . . .. . . . · . . (39) 0 1 0 · · · ... · · · 0 1 .. .. · · . . · · 0 1
and the sum of its columns gives the vector full of ones. We now perform two types of column operations in the skeleton matrix. First, we sum all the u columns associated with the edge E− to obtain a vector full of ones on top and full of zeros at its bottom, and subtract it from the first columns of B. We note B ′ the results of such an u operation. Then, we add the columns associated with the set E+ to the first columns of B ′ and
19
note B̃ the result of this operation. The corresponding matrix are 0 0 0 0 ... 0 . .. .. .. . . . . .. A1 0 M1 .. . . . 0 0 0 0 ... 0 0 1 −1 1 . . . 0 . .. .. .. .. A .. . 0 M2 2 . . . . . . ′ B = −1 1 . . . 0 , B̃ = 0 1 .. · · · · · . · · · 0 ... −1 . . . 0 1 . . .. .. .. A .. .. .. 0 M−1 −1 . . . . 0 ... −1 . . . 0 1 0 0 0 0 0 0 0 D ·
... .. . ... ... .. . ...
0 .. . 0 0 .. . 0
· 0 .. . 0 0
· 1 .. . 1 0
A1
0
M1
A2
0
M2
·
.. .
·
A−1
0
M−1
0
D
·
Where the modifications are indicated in red. We see in the matrix B̃ that the connection e↔ has been removed in the sense that the column which was previously associated with it is full of zeros. 2. Transform nu in an output node We now transform B̃ into a skeleton matrix of a network with h − 1 hidden neurons. To do so, we should remove in B̃ the ones corresponding to the end of the paths crossing the edge e↔ and not ending ad node nk . This part of the proof is similar to the induction’s initialization. Let P the set of path crossing e↔ and not ending at nk . We take advantage of the choice of node u in the topological sort with the following lemma. Lemma 8. Consider a graph whose node indices are ordered with a topological sort, and let k an output node such that for all k ′ > k node k ′ is an output node, then, for any p of length l ≥ 2 if p crosses node k and not ending at k it exists a path p̃ of size l − 1 that coincide with p on its l − 1 first nodes. As a consequence : Proof:8 B̃[p, :] − B̃[p̃, :] = (0
·
0
1
0
·
0)
(40)
where the only non-null element corresponds to the last edge crossed by path p.
Proof. The proof is the same as the proof of lemma 5 the only difference is that we should consider matrix B̃. Considering the writting of B̃, we see that the only difference is that the column associated with the edge e↔ is full of zeros, thus one can replace B by B̃ and the result still holds. We now perform row operations on B̃ with algorithm 6.
Data: B̃ the modified skeleton matrix, P the list of path crossing edge e↔ and not ending at node nk , lmin , lmax the minimum and maximum length of a path in P. Result: matrix B̃ ′ of the same rank as B̃ for l ∈ {lmax , lmax − 1, · · · , lmin } do for p ∈ P and p of length l do Let p̃ be the path of lemma 8 coinciding with p on its l − 1 first nodes. B̃[p, :] ← B̃[p, :] − B̃[p̃, :] end end Algorithm 6: Row operations on matrix B̃
20
The matrix B̃ ′ outputted by algorithm 6 is of the same rank as B̃. Let E end be the set of edges corresponding to the last edge of a path in P. For each edge e in E end , there exists a row in B̃ ′ such that the only non-null element of the row is at edge e (lemma 8 and algorithm 6). Using this property, we remove in B̃ ′ the dependency of all edge e in E end for the paths not in P. We perform such operations and obtain the matrix F . Ordering its columns starting with the set of edges E end , and e↔ , this matrix is of the form
F =
E end A 0 0
e↔ ! 0 0 0 H 0 D
where the rows (A 0 0) corresponds to the rows with only one non-null element by row each of them corresponding to an edge in E end ; where the rows (0 0 H) corresponds to the paths ending at node nu , and the rows (0 0 D) correspond to all the path that are not ending at node nu or not crossing node nu and whose dependency on the edges in E end has been removed using the rows of A. It follows that H ′ rk(B̃ ) = rk(F ) = rk(A) + rk( ). D H end Remark that rk(A) = #E and that the matrix coincide with the skeleton matrix of a D network with h − 1 hidden nodes and with d − 1 − #E end parametersup to null and repeated H rows, which do not affect the rank. Using the induction on the matrix it follows that D rk(B) = rk(B̃ ′ ) = #E end + d − #E end − 1 − (h − 1) =d−h. H Remark that the reduced graph associated to the matrix may contain nodes that lose all D end their incoming edges (when the edges in E are deleted) and would then be re-classified as input nodes by Definition of I, however this does not affect the rank of matrix F .
B
Experiment and python module
B.1
Experiment settings
The experiment has been run on the Intel Xeon Gold 6226R CPU. The used precision is float32, and the main Python library is pytorch version 2.6.0. B.2
Python module
The Python code is available at this gitLab. The two main implementations of the module are the construction of the pathlifting and the skeleton matrix for arbitrary feed-forward networks. Both functions are implemented in the Python file PythonFiles/PathLiftingAndSkeleton.py. • The pathlifting is constructed as a tensor object of dimension (q, P1 ), where P1 is the number of paths going to one output node. Its construction is done following the pseudo code 11. • The skeleton is constructed as a tensor object of dimension (q, P1 , d) where d is the number of parameters in the network. Its construction is done following the pseudo code 12. 21
With this tensor form of Φ and B, the Jacobian ∂θ Φ(θ) can be computed the modifyed version of algorithm 7 that is as follows. Data: θ the current parameters.ϕ := the pathlifting at point θ, B the skeleton matrix Result: J the Jacobian of ϕ at θ u ← θ1 ; J = torch.einsum(′ qP1 , qP1 d, d− > qP1 d ′ , ϕ, B, u); Algorithm 7: Jacobian of Φ(θ) with B as tensor Both functions use the auxiliary function ListOfPathsAsNodesAtLayer described in algorithm 8, in which the Cartesian product is computed using the itertools Python library. We also remark that both implementations can be enhanced using recursive approaches. The dimensions are summarized in table 2.
Dimension q L d P1 (q, P1 ) (q, P1 , d)
Table 2: Dimensions Description number of output nodes depth of the network dimension of the network parameter number of paths ending at one output node dimension of the pathlifting as a tensor dimension of the skeleton as a tensor
Data: LayersList: list of ordered network layers, l0 a layer index, IsBias:Boolean indicating if the starting node is a bias node Result: All possible paths (represented as lists of nodes) starting from layer l0 SelectedLayers ← ∅ if l0 = 1 and not(IsBias) then // For bias node, we do not consider the starting node of the path SelectedLayers ← { n | n ∈ LayersList[1].in f eatures } end for k ← l0 to L do SelectedLayers.append { n | n ∈ LayersList[k].out f eatures} end P athsAsN odes ← C ARTESIAN P RODUCT(SelectedLayers) return P athsAsN odes Algorithm 9: ListOfPathsAsNodesAtLayer
22
Data: LayersList: ordered list of network layers, θ: network parameters Result: Pathlifting tensor Φ(θ) Φ ← 1q×P1 StoredP aths = {} foreach output node q do StoredP aths[q] ← 0 end P athsAsN odes ← L IST O F PATHS A S N ODES AT L AYER(1, F alse) // Paths starting from the input layer foreach N odesList ∈ P athsAsN odes do qp ← last node of N odesList ip ← StoredP aths[qp ] for j ← 0 to |N odesList| − 2 do k ← index of the parameter connecting N odesList[j] and N odesList[j + 1] Φ[qp , ip ] ← Φ[qp , ip ]θ[k] end StoredP aths[qp ] ← StoredP aths[qp ] + 1 end // Paths starting from a bias node at layer l ≥ 2 for l ← 2 to L do P athsAsN odes ← L IST O F PATHS A S N ODES AT L AYER(l, T rue) foreach N odesList ∈ P athsAsN odes do qp ← last node of N odesList ip ← StoredP aths[qp ] b ← index of parameter connecting the bias node to the first node in N odesList Φ[qp , ip ] ← θb for j ← 0 to |N odesList| − 2 do k ← index of the parameter connecting N odesList[j] and N odesList[j + 1] Φ[qp , ip ] ← Φ[qp , ip ] · θ[k] end StoredP aths[qp ] ← StoredP aths[qp ] + 1 end end return Φ Algorithm 11: PathLifting
23
Data: LayersList: ordered list of network layers, θ: network parameters Result: Skeleton tensor B B ← 0q×P1 ×d StoredP aths = {} foreach output node q do StoredP aths[q] ← 0 end P athsAsN odes ← L IST O F PATHS A S N ODES AT L AYER(1, F alse) // Paths starting from the input layer foreach N odesList ∈ P athsAsN odes do qp ← last node of N odesList ip ← StoredP aths[qp ] for j ← 0 to |N odesList| − 2 do k ← index of the edge connecting N odesList[j] and N odesList[j + 1] B[qp , ip , k] ← 1 end StoredP aths[qp ] ← StoredP aths[qp ] + 1 end // Paths starting from a bias node at layer l ≥ 2 for l ← 2 to L do P athsAsN odes ← L IST O F PATHS A S N ODES AT L AYER(l, T rue) foreach N odesList ∈ P athsAsN odes do qp ← last node of N odesList ip ← StoredP aths[qp ] b ← index of parameter connecting the bias node to the first node in N odesList B[qp , ip , b] ← 1 for j ← 0 to |N odesList| − 2 do k ← index of the edge connecting N odesList[j] and N odesList[j + 1] B[qp , ip , k] ← 1 end StoredP aths[qp ] ← StoredP aths[qp ] + 1 end end return B Algorithm 12: SkeletonMatrix
24