# Chordal directed graphs are not directed $\chi$-bounded

Pierre Aboulker1, Nicolas Bousquet2, Rémi de Verclos3
($1$) DIENS, École normale supérieure, CNRS, PSL University, Paris, France.
<EMAIL_ADDRESS>
($2$) Univ. Lyon, Université Lyon 1, LIRIS, UMR CNRS 5205, F-69621, Lyon,
France
<EMAIL_ADDRESS>
($3$<EMAIL_ADDRESS>
###### Abstract

We show that digraphs with no transitive tournament on $3$ vertices and in
which every induced directed cycle has length $3$ can have arbitrarily large
dichromatic number. This answers to the negative a question of Carbonero,
Hompe, Moore, and Spirkl (and strengthens one of their results).

##  1 Introduction

Throughout this paper, we only consider simple graphs (resp. directed graph)
$G$, that is, for every two distinct vertices $u$ and $v$, the graph $G$ does
not have multiple edges (resp. both arcs $uv$ and $vu$).

Relations between the chromatic number $\chi(G)$ and the clique number
$\omega(G)$ of a graph $G$ have been studied for decades in structural graph
theory. In particular, it is well known that there exist triangle-free graphs
$G$ with arbitrarily large chromatic number (see e.g. [3, 9]). A hereditary
class of graphs is _$\chi$ -bounded_ if there exists a function $f$ such that
for every $G\in\mathcal{G}$, $\chi(G)\leq f(\omega(G))$ (see e.g. a recent
survey [7] on the topic). The following question received considerable
attention in the last few years: Consider a hereditary class of graphs
$\mathcal{G}$ in which every triangle-free graph has bounded chromatic number.
Is it true that $\mathcal{G}$ is $\chi$-bounded? Carbonero, Hompe, Moore and
Spirkl [2] answered to it by the negative in a recent breakthrough paper.

Their initial motivation was actually to prove a result on digraphs. Let $D$
be a digraph. A $k$-dicolouring of $D$ is a $k$-partition
$(V_{1},\dots,V_{k})$ of $V(D)$ such that $D[V_{i}]$ is acyclic for every
$1\leq i\leq k$. Such a partition is also called an _acyclic colouring_ of
$D$. The dichromatic number of $D$, denoted by $\vec{\chi}(D)$ and introduced
by Neumann-Lara in [6], is the smallest integer $k$ such that $D$ admits a
$k$-dicolouring. We denote by $\omega(D)$ the size of a largest clique in the
underlying graph of $D$. We call directed triangle the directed cycle of
length $3$. As for unoriented graphs, we say that a hereditary class of
digraphs $\mathcal{G}$ is _$\vec{\chi}$ -bounded_ if for every
$G\in\mathcal{G}$, $\vec{\chi}(G)\leq f(\omega(G)$.

Carbonero, Hompe, Moore and Spirkl [2] proved that the class of digraphs with
no induced directed cycle of odd length at least $5$ is not
$\vec{\chi}$-bounded by giving a collection of digraphs with no induced
directed cycle of odd length at least $5$, no $K_{4}$ and with arbitrarily
large dichromatic number. They ask (Question 3.2) if the class of digraphs in
which every induced directed cycle has length $3$ is $\vec{\chi}$-bounded.
These digraphs can be seen as directed analogues of chordal graphs, where a
chordal directed graph is a directed graph with no induced directed cycle of
length at least $4$.

We answer negatively to this question (and thus strengthen the construction of
[2]). Let us denote by $TT_{3}$ the _transitive tournament_ on $3$ vertices
(i.e. the triangle which is oriented acyclically). Let $\mathcal{C}_{3}$ be
the class of digraphs with no $TT_{3}$ nor induced directed cycle of length at
least $4$. We prove the following.

######  Theorem 1.

For every $k$, there exists $G\in\mathcal{C}_{3}$ such that $\vec{\chi}(G)\geq
k$.

Since any orientation of a $K_{4}$ contains a $TT_{3}$, it answers Question
3.2 of [2].

##  2 Proof of Theorem 1

Our proof technique can be seen as a generalization of the construction of
triangle-free graphs with arbitrarily large chromatic number due to Zykov [9].
Assume that we are given a triangle-free graph $G_{k}$ with chromatic number
at least $k$, and let us define $G_{k+1}$ as follows (note that we can set
$G_{1}$ as a single vertex graph). Let $G$ be the graph made of $k$ disjoint
copies of $G_{k}$. Set $\mathcal{I}$ to be the set of all $k$-subsets of
vertices of $G$ containing exactly one vertex in each copy of $G_{k}$. Now,
build the graph $G_{k+1}$ from $G$ as follows: for every set
$I\in\mathcal{I}$, create a new vertex $x_{I}$ adjacent to every vertex in
$I$. The key observation is that, for any colouring of $G_{k+1}$, for each
$I\in\mathcal{I}$, the vertex $x_{I}$ forces $I$ to miss at least one colour,
namely the one received by $x_{I}$. This easily implies that $G_{k+1}$ is not
$k$-colourable. Indeed, if one tries to $k$-colour $G_{k+1}$, since $G_{k}$
has chromatic number $k$, there must be a vertex $x_{i}$ coloured $i$ in the
$i^{th}$ copy of $G_{k}$ for every $i\leq k$. A contradiction with the key
observation above. Moreover, since each set of $\mathcal{I}$ is an independent
set, $G_{k+1}$ is triangle-free.

For digraphs, such a naive construction fails since adjacent vertices are
allowed to receive the same colour. A way to force a given independent set $I$
of a digraph $D$ to avoid a colour (without creating induced directed cycle of
length at least $4$ nor $TT_{3}$) is to connect each vertex of $I$ to an arc
$uv$ (instead of a single vertex as in the directed case) in such a way that
each vertex of $I$ forms a directed triangle with $uv$ and then hope that the
two vertices $u$ and $v$ receive the same colour. Unfortunately we cannot
force an arc to have both endpoints of the same colour. But we have for a
slightly weaker property, namely:

######  Remark 1.

Let $G\in\mathcal{C}_{3}$ be a directed graph with at least one arc. Any
$\vec{\chi}(G)$-dicolouring of $G$ contains at least one monochromatic arc.

###### Proof.

The result trivially holds if $\vec{\chi}(G)=1$, so we may assume that
$\vec{\chi}(G)\geq 2$. Let $V_{1},\dots,V_{\vec{\chi}(G)}$ be a
$\vec{\chi}(G)$-dicolouring of $G$. The set $V_{1}\cup V_{2}$ must contain an
induced directed cycle $C$ since otherwise $G$ would be
$(\vec{\chi}(G)-1)$-colourable. (Indeed, a colouring of the vertices of a
digraph is acyclic if and only if none of its induced directed cycle is
monochromatic). Hence, by definition of $\mathcal{C}_{3}$, $V_{1}\cup V_{2}$
contains a directed triangle, and an arc of this directed triangle must have
both endpoints in $V_{1}$ or both endpoints in $V_{2}$. ∎

Let $G$ be a $k$-chromatic digraph and $I$ be an independent set of $G$. Using
Remark 1, we prove that we can create a graph $G^{\prime}$ containing many
copies of $G$ such that, for every $k$-coloring of $G^{\prime}$, there is one
copy of $G$ in $G^{\prime}$ where the vertices of $I$ (in that copy) miss at
least one color (Lemma 2). We then extend this result for arbitrarily many
independent sets (Lemma 3). We then prove Theorem 1 using Lemma 3 as in
Zykov’s construction.

######  Lemma 2.

Let $k$ be an integer. Let $G\in\mathcal{C}_{3}$ with $n$ vertices and $m$
arcs, and such that $\vec{\chi}(G)=k$. Let $I$ be an independent set of $G$.
Then there exists a digraph $H\in\mathcal{C}_{3}$ such that $H$ contains $m$
pairwise disjoint copies $G_{1},\ldots,G_{m}$ of $G$ and satisfy the
following:

  * •

For every $1\leq i\neq j\leq m$, there is no arc between $G_{i}$ and $G_{j}$;

  * •

For every $k$-dicolouring of $H$, there exists an index $i\leq m$ and a colour
$\alpha$ such that no vertex of the copy of $I$ in $G_{i}$ is coloured with
$\alpha$.

Moreover $H$ has $n\cdot(m+1)\leq n^{4}$ vertices and at most
$m(m+1)+mn^{2}\leq n^{4}$ arcs.

###### Proof.

Let us first describe the construction of $H$. We first create $m+1$ pairwise
disjoint copies of $G$ denoted by $G_{1},\dots,G_{m},G_{m+1}$. For every
$i\leq m$, let $I_{i}$ be the copy of $I$ in $G_{i}$. Let us denote
$u_{1}^{m+1}v_{1}^{m+1},\dots,u_{m}^{m+1}v_{m}^{m+1}$ the arcs of $G_{m+1}$.
We add in $H$ some arcs between the $G_{i}$ ($i\leq m$) and $G_{m+1}$ as
follows. For every $i\leq m$ and for every vertex $x\in I_{i}$, add the arcs
$v_{i}^{m+1}x$ and $xu_{i}^{m+1}$ in $H$.

Observe that $H$ has $n\cdot(m+1)$ vertices and $m\cdot(m+1)+2m\cdot|I|\leq
n^{4}$ arcs as announced.

By construction, for every $1\leq i\neq j\leq m$, there is no arc between
$G_{i}$ and $G_{j}$, so the first bullet holds.

Let $c$ be a $k$-dicolouring of $H$. By Remark 1, $G_{m+1}$ has a
monochromatic arc, say $u_{i}^{m+1}v_{i}^{m+1}$. Let $\alpha$ be the colour of
$u_{i}^{m+1}$ and $v_{i}^{m+1}$ in $c$. Then, for every vertex $x\in I_{i}$,
$x$ is not coloured with $\alpha$ since $H[\\{u_{i},v_{i},x\\}]$ is a directed
triangle. This proves the second bullet.

To conclude, we simply have to prove that $H\in\mathcal{C}_{3}$. First assume
for contradiction that $H$ contains a copy $X$ of a $TT_{3}$ as a subgraph.
Since there is no arc between $G_{i}$ and $G_{j}$ for $1\leq i\neq j\leq m$,
$X$ intersects at most one of the graphs $G_{i}$ for $i\leq m$. Moreover,
since $G$ is in $\mathcal{C}_{3}$, $X$ is not included in $G_{i}$ for $i\leq
m+1$. So $X$ must intersect $G_{m+1}$ and some $G_{i}$ for some $i\leq m$.
Assume first that $X$ contains two vertices of $G_{m+1}$. By construction, the
only vertices of $G_{m+1}$ connected to $G_{i}$ are $u_{i}^{m+1}$ and
$v_{i}^{m+1}$. So both vertices are in $X$. Moreover, the only vertices of
$G_{i}$ connected to $G_{m+1}$ are the vertices of $I_{i}$ so the third vertex
must be a vertex $x$ of $I_{i}$. But by construction,
$G[\\{x,u_{i}^{m+1},v_{i}^{m+1}\\}]$ is a directed triangle, a contradiction.
So we can assume that $X$ contains two vertices of $G_{i}$. Since $X$ is a
$TT_{3}$, they must be adjacent and both be adjacent to a vertex of $G_{m+1}$.
But, by construction, the only vertices of $G_{i}$ connected to $G_{m+1}$ are
the vertices of $I_{i}$ which is an independent set, a contradiction. So $H$
contains no $TT_{3}$.

Finally, assume for contradiction that $H$ contains a directed cycle $C$ of
length at least $4$ as an induced subgraph. Since $G\in{\mathcal{C}_{3}}$, $C$
is not contained in $G_{i}$ for $i=1,\dots,m+1$. Since there is no arc between
$G_{i}$ and $G_{j}$ for $1\leq i\neq j\leq m$, the cycle $C$ intersects
$G_{m+1}$ and we may assume without loss of generality that $C$ also
intersects $G_{1}$. So $C$ contains $u_{1}^{m+1}$ or $v_{1}^{m+1}$. Since, by
construction, $u_{1}^{m+1}$ has no out-neighbour in $G_{1}$ and $v_{1}^{m+1}$
has no in-neighbour in $G_{1}$, $C$ must contain both $u_{1}^{m+1}$ and
$v_{1}^{m+1}$ (since the deletion of $u_{1}^{m+1}$ and $v_{1}^{m+1}$
disconnects $G_{1}$ from the rest of the graph). But now all the vertices of
$G_{1}$ incident to $u_{1}$ or $v_{1}$ are the vertices $x$ of $I$. And by
construction, for every $x\in I$, $H[\\{u_{1}^{m+1},v_{1}^{m+1},x\\}]$ is a
directed triangle, a contradiction. ∎

######  Lemma 3.

Let $k,r$ be two integers. Let $G\in\mathcal{C}_{3}$ such that
$\vec{\chi}(G)=k$ and let $I_{1},\ldots,I_{r}$ be $r$ independent sets of $G$.
There exist an integer $\ell_{r}$ and a digraph $H\in\mathcal{C}_{3}$ such
that $H$ contains $\ell_{r}$ pairwise disjoint copies
$G_{1},\ldots,G_{\ell_{r}}$ of $G$ such that:

  * •

For every $1\leq i\neq j\leq m$, there is no arc between $G_{i}$ and $G_{j}$;

  * •

For every $k$-dicolouring of $H$, there exists an index $j\leq\ell_{r}$ such
that, for every $s\leq r$, there exists a colour $\alpha_{s}$ such that no
vertex of the copy of $I_{s}$ in $G_{j}$ is coloured with $\alpha_{s}$.

Moreover $H$ contains at most $n^{4r}$ vertices and arcs.

###### Proof.

We now have all the ingredients to prove Lemma 3 by induction on $r$. By Lemma
2, the case $r=1$ holds.

Assume that the conclusion holds for $r\geq 1$ and let us prove the result for
$r+1$. Let $G\in\mathcal{C}_{3}$ with $\vec{\chi}(G)=k$ and let
$I_{1},\ldots,I_{r+1}$ be $r+1$ independent sets of $G$. By induction applied
on $G$ and independent sets $I_{1},\dots,I_{r}$, there exists an integer
$\ell_{r}$ and a digraph $H_{r}\in\mathcal{C}_{3}$ such that $H_{r}$ contains
$\ell_{r}$ pairwise disjoint copies $G_{1},\ldots,G_{\ell_{r}}$ of $G$ such
that:

  * •

For every $1\leq i\neq j\leq\ell_{r}$, there is no arc between $G_{i}$ and
$G_{j}$;

  * •

For every $k$-dicolouring of $H_{r}$, there exists an index $j\leq\ell_{r}$
such that, for $s=1,\dots,r$, there exists a colour $\alpha_{s}$ such that no
vertex of the copy of $I_{s}$ in $G_{j}$ is coloured with $\alpha_{s}$.

Note that by induction, $H_{r}$ has at most $n^{4r}$ vertices and edges. Let
us denote by $J$ the union of the vertices of the copies of $I_{r+1}$ in the
subgraphs $G_{1},\ldots,G_{\ell_{r}}$ and observe that $J$ is an independent
set. By Lemma 2 applied on $H_{r}$ and $J$, there exists a digraph
$H_{r+1}\in\mathcal{C}_{3}$ that contains $m=|E(H_{r})|$ pairwise disjoint
copies $H^{1}_{r},\ldots,H_{r}^{m}$ of $H_{r}$ such that:

  * •

For $1\leq i\neq j\leq m$, there is no arc between $H^{i}_{r}$ and
$H_{r}^{j}$;

  * •

For every $k$-dicolouring of $H_{r+1}$, there exists an index $j\leq m$ and a
colour $\alpha_{r+1}$ such that no vertex of the copy of $J$ in $H_{r}^{j}$ is
coloured with $\alpha_{r+1}$.

Moreover, $H$ has at most $|V(H_{r})|^{4}=n^{4(r+1)}$ vertices and arcs.

Let us prove that $H_{r+1}$ satisfies the conclusion of Lemma 3. For every
$i\leq m$, $H_{r}^{i}$ being a copy of $H_{r}$, it contains $\ell_{r}$ copies
of $G$, denoted by $G^{i}_{1},\dots,G^{i}_{\ell_{r}}$. Thus, by construction
of $H_{r+1}$, the graph $H_{r+1}$ contains $\ell_{r+1}:=m\cdot\ell_{r}$
induced copies of $G$ and by construction there is no arc linking any of these
copies.

Fix a $k$-dicolouring of $H_{r+1}$. There exists an index $j\leq m$ and a
colour $\alpha_{r+1}$ such that no vertex of the copy of $J$ in $H_{r}^{j}$ is
coloured $\alpha_{r+1}$. Since $H_{r}^{j}$ is a copy of $H_{r}$ there exists
an index $k\leq\ell_{r}$ such that, for $s=1,\dots,r$, there exists a colour
$\alpha_{s}$ such that no vertex of the copy of $I_{s}$ in $G^{j}_{k}$ is
coloured with $\alpha_{s}$. Hence, the second bullet holds, which completes
the proof. ∎

###### Proof of Theorem 1.

Let us construct a sequence $(G_{k})_{k\in\mathbb{N}}$ such that for every
$k$, $G_{k}\in\mathcal{C}_{3}$ and $\vec{\chi}(G_{k})\geq k$. Let $G_{1}$ be
the graph reduced to a single vertex and let $G_{2}$ be the directed triangle.
Let $k\geq 2$ and assume that we have obtained a $k$-dichromatic digraph
$G_{k}$ which is in ${\mathcal{C}_{3}}$, let us define $G_{k+1}$ as follows.
Let $G$ be the digraph consisting of $k$ disjoint copies of $G_{k}$, denoted
by $G_{k}^{1},\ldots,G_{k}^{k}$. Let $\mathcal{I}$ be the set of independent
sets that intersect each $G_{k}^{i}$ on a single vertex. Since
$\vec{\chi}(G_{k})\geq k$, in any $k$-dicolouring of $G$, there exists a
vertex $x_{i}$ coloured $i$ in $G_{k}^{i}$ for every $i=1,\dots,k$. By
definition of $\mathcal{I}$, $\\{x_{1},\ldots,x_{k}\\}\in\mathcal{I}$. Hence,
for every $k$-dicolouring of $G$, a set of $\mathcal{I}$ receives all the
colours.

By Lemma 3 applied on $G$ and $\mathcal{I}$, there exists a digraph
$G_{k+1}\in\mathcal{C}_{3}$ such that, for every $k$-dicolouring of $G_{k+1}$
(if such a colouring exists), there exists a copy of $G$ in $G_{k+1}$ such
that each set $\mathcal{I}$ in that copy of $G$ avoids a colour, a
contradiction. So $\vec{\chi}(G_{k+1})\geq k+1$. ∎

##  3 Further works

Our $(k+1)$-dichromatic graph has size $n^{2^{poly(n)}}$, which is larger than
the graphs obtained using Zykov’s construction which have size of order
$2^{poly(|G_{k}|)}$. It would be interesting to know if the size of our
example can be reduced.

One can wonder if directed triangles play a particular role in Theorem 1. More
formally, one can wonder (as also asked in [2], Question 3.3) for which
integer $k$, the class of digraphs which only contain induced directed cycles
of length exactly $k$ are $\vec{\chi}$-bounded. Our main result is that it is
not the case for $k=3$. We left the problem open for $k\geq 4$.

On the same flavour, we recall here the following conjecture of Aboulker,
Charbit and Naserasr which can be seen as a directed analogue of the well-
known Gyárfás-Sumner conjecture [4, 8]. An oriented tree is an orientation of
a tree.

######  Conjecture 1.

[1] For every oriented tree $T$, the class of digraphs with no induced $T$ is
$\vec{\chi}$-bounded.

Acknowledgments: This research was supported by ANR project DAGDigDec (JCJC)
ANR-21-CE48-0012.

## References

  * [1] P. Aboullker, P. Charbit, and R. Naserasr.  Extension of gyárfás-sumner conjecture to digraphs.  The Electronic Journal of Combinatorics, 18(2), 2021.
  * [2] Alvaro Carbonero, Patrick Hompe, Benjamin Moore, and Sophie Spirkl.  A counterexample to a conjecture about triangle-free induced subgraphs of graphs with large chromatic number.  arXiv preprint:2201.08204, 2022.
  * [3] Blanche Descartes.  A three colour problem.  Eureka, 9(21):24–25, 1947.
  * [4] A. Gyárfás.  On ramsey covering-numbe.  In Infinite and finite sets (Colloq., Keszthely, 1973; dedicated to P. Erdős on his 60th birthday, pages 801–816. Colloq. Math. Soc. Janos Bolyai 10, North-Holland, Amsterdam, 1975.
  * [5] A. Gyárfás.  “on ramsey covering-numbe.  , Infinite and finite sets (Colloq., Keszthely, 1973; dedicated to P. Erdőos on his 60th birthday, II, 1975.
  * [6] V. Neumann-Lara.  The dichromatic number of a digraph.  Journal of Combinatorial Theory, Series B, 33(3):265 – 270, 1982\.
  * [7] A. Scott and P. Seymour.  A survey of $\chi$-boundedness.  Journal of Graph Theory, 95(3), 2020.
  * [8] D. P. Sumner.  Subtrees of a graph and chromatic number.  In The Theory and Applications of Graphs, (G. Chartrand, ed.), pages 557–576, New York, 1981. John Wiley & Sons.
  * [9] A. Zykov.  On some properties of linear complexes (in russian).  Mat. Sbornik N.S., 24(66), 1949.


# Any Deep ReLU Network is Shallow

Mattia J. Villani
Department of Informatics
King’s College London
London WC2B 4BG
<EMAIL_ADDRESS>
&Nandi Schoots
Department of Informatics
King’s College London
London WC2B 4BG
<EMAIL_ADDRESS>
###### Abstract

We constructively prove that every deep ReLU network can be rewritten as a
functionally identical three-layer network with weights valued in the extended
reals. Based on this proof, we provide an algorithm that, given a deep ReLU
network, finds the explicit weights of the corresponding shallow network. The
resulting shallow network is transparent and used to generate explanations of
the model’s behaviour.

##  1 Introduction

Deep learning systems are leveraged for their flexibility and performance to
solve real world tasks efficiently; yet, their complexity warrants in-depth
analysis to provide safety and soundness guarantees. In light of this, we
present a method to convert black-box neural networks into functionally
identical shallow white-box networks.

Our contributions are:

  1. 1.

A constructive proof of the existence of a functionally identical shallow
network (three hidden layers) with weights in the extended reals for every
deep ReLU network (Section 3);

  2. 2.

An algorithm to find the values of these weights given a trained network
(Section 4), which relies on searching the space of possible neuron
activations through heuristics that we prove to be exhaustive; and

  3. 3.

Explainability improvements that arise from the shallow network construction
(Section 5) including fast SHAP values.

Our constructive proof permits explicit specification of the weights, thus
enabling us to compute the shallow network algorithmically. The code for
replicating our experiments is provided in the Appendix.

This work builds on recent breakthroughs that exactly represent ReLU networks
as collections of local linear models. Sudjianto et al. (2020) find explicit
weights of local linear models for ReLU networks as a function of the weights.
Other works compute local approximations of neural networks as explanations
(Dong et al., 2021), or use them to analyse phenomena such as dying neurons
(Jiang et al., 2022). Conversely, He et al. (2021) proves that every piece-
wise linear function on a bounded domain can be realised as a ReLU network of
a given depth, provided as a function of the linear regions.

This study extends these findings by enhancing the theoretical understanding
of neural networks and establishing a firm connection between linear
programming and ReLU activation patterns. Consequently, our work advances
global interpretability of neural networks and provides effective heuristics
for exploring the extensive search space of activation patterns.

##  2 Background

We restrict our analysis to architectures which are feed-forward neural
networks; in particular, those whose activation function for each layer is the
rectifier linear unit (ReLU), but generalize our findings in Corollary 3 to
other ReLU-based architectures.

######  Definition 1 (ReLU Network).

A ReLU network $\mathcal{N}\colon\mathbb{R}^{n}\rightarrow\mathbb{R}^{m}$, is
a composition of $L\in\mathbb{N}$ hidden layers given by:

$\chi^{(l)}=\sigma({W^{(l)}}\chi^{(l-1)}+b^{(l)}),$

where $\sigma$ is an element-wise ReLU activation function,
$\sigma(x_{i})=\max\\{0,x_{i}\\}$. We define $\chi^{(0)}=x$ and the output
layer is given by $\mathcal{N}(x)=W^{(L+1)}\chi^{(L)}+b^{(L+1)}$. The number
of neurons in each layer is given by a vector
$\mathbf{N}=[n_{1},n_{2},\ldots,n_{L}]$, and all activations are in the
positive reals, i.e. $\chi^{(l)}\in\mathbb{R}^{n_{l}}_{\geq 0}$ for all
$l\in\\{1,\ldots,L\\}=[L]$. We stress the dependence on $x$ by writing
$\chi^{(l)}(x)$.

We can describe these functions as linear models that are applied to certain
regions of the input space (Sudjianto et al., 2020). Moreover, these regions
partition $\mathbb{R}^{n}$.

######  Example 1.

Consider the network given by the weight matrix $W=\begin{bmatrix}1&1\\\
1&0\end{bmatrix}.$ Let the input vector be $\begin{bmatrix}x_{1}\\\
x_{2}\end{bmatrix}$. Then, the output of this network, after applying the ReLU
activation function, is $\begin{bmatrix}y_{1}\\\
y_{2}\end{bmatrix}=\text{ReLU}\left(\begin{bmatrix}1&1\\\
0&1\end{bmatrix}\begin{bmatrix}x_{1}\\\
x_{2}\end{bmatrix}\right)=\text{ReLU}\left(\begin{bmatrix}x_{1}+x_{2}\\\
x_{2}\end{bmatrix}\right)=\begin{bmatrix}\max(0,x_{1}+x_{2})\\\
\max(0,x_{2})\end{bmatrix}.$

This gives us a partition of the input space $\mathbb{R}^{2}$. The boundaries
are determined by the points where the vector output of the linear
transformation has entries equal to zero.

Then, the four parts (or regions) are given by:

$\omega_{1}=\\{(x_{1},x_{2}):x_{1}+x_{2}>0,x_{2}>0\\},\omega_{2}=\\{(x_{1},x_{2}):x_{1}+x_{2}\leq
0,x_{2}>0\\},$ $\omega_{3}=\\{(x_{1},x_{2}):x_{1}+x_{2}>0,x_{2}\leq
0\\},\omega_{4}=\\{(x_{1},x_{2}):x_{1}+x_{2}\leq 0,x_{2}\leq 0\\},$

such that $\Omega=\\{\omega_{1},\omega_{2},\omega_{3},\omega_{4}\\}$ covers
the input space.

######  Proposition 1.

[Sudjianto et al. (2020)] For a ReLU network
$\mathcal{N}\colon\mathbb{R}^{n}\rightarrow\mathbb{R}^{m}$ there is a finite
partition $\Omega$ of $\mathbb{R}^{n}$ of cardinality $p:=\\#\Omega$ such that
for each part $\omega\in\Omega$ there exists a piece-wise linear function
$f\colon\mathbb{R}^{n}\rightarrow\mathbb{R}^{m}$, and its restriction on
$\omega$, denoted $f|_{\omega}$, can be described by a linear function:

$f|_{\omega}(x)=\alpha_{\omega}^{T}x+\beta_{\omega}.$

Moreover, each part is a polytope, given by the intersection of a collection
of half-spaces. We write the minimum set of half-space conditions that can be
used to specify the entire partition as $H_{1},\ldots,H_{k}$, where each
$H_{i}$ is given by the set of all $x\in\mathbb{R}^{n}$ such that:

$h_{i,1}x_{1}+h_{i,2}x_{2}+\ldots+h_{i,n}x_{n}>c_{i}.$

To represent the decomposition and linear models, it is useful to characterise
the states of a neural network by looking at which neurons are active and
inactive in all layers.

######  Definition 2 (Activation Pattern).

For a given ReLU network
$\mathcal{N}\colon\mathbb{R}^{n}\rightarrow\mathbb{R}^{m}$ with neuron
dimensionality vector $\mathbf{N}=[n_{1},\ldots,n_{L}]$, the activation
pattern at a point $x\in\mathbb{R}^{n}$ is a collection of vectors
$P=\\{P^{(1)},\ldots,P^{(L)}\\}$, with $P^{(l)}\in\\{0,1\\}^{n_{l}}$ for each
$l\in[L]$, such that for all $i\in[n_{l}]$,

$P^{(l)}_{i}=1\iff\chi^{(l)}_{i}(x)>0.$

##  3 Finding a Shallow Network for a given Piece-wise Linear Function

Figure 1 illustrates the intuition that a network can be fully characterized
by 1) the partition; and 2) a linear model for each item in the partition.
This suggests that we can convert any deep network into a shallow one. We will
now formalize and prove this intuition.

Figure 1: A high-level representation of the conversion of a deep ReLU network
(left) using a decomposition of the input space into regions that each have
their own linear model (middle) to a shallow ReLU network (right).

######  Theorem 1.

For every ReLU network
$\mathcal{N}\colon\mathbb{R}^{n}\rightarrow\mathbb{R}^{m}$, there exists a
shallow ReLU network
$\mathcal{S}\colon\mathbb{R}^{n}\rightarrow\mathbb{R}^{m}$ of depth $L=3$,
with weights in the extended reals
$\bar{\mathbb{R}}=\mathbb{R}\cup\\{\infty\\}$ such that for all
$x\in\mathbb{R}^{n}$, the following holds:

$\mathcal{N}(x)=\mathcal{S}(x).$

###### Proof.

Our strategy will be to build a first layer that encodes the linear models and
the half-spaces that span the partition. We will use the weights that encode
the half-spaces to, in the last layer, select the correct linear model out of
the list of linear models. See Figure 2 for an overview of the components of
the shallow network.

Figure 2: A schematic representation of the shallow network.

Let $(\\{f_{\omega}\\}_{\omega\in\Omega},\Omega)$ be the decomposition that
corresponds to $\mathcal{N}$. Label the parts $1,\ldots,p$. Recall that each
part is a polytope and we can represent it as the intersection of half-spaces.
In particular, let $H_{1},\ldots,H_{k}$ be the the minimum set of half-spaces
that specify the partition, where each $H_{i}$ is given by the set of all
$x\in\mathbb{R}^{n}$ such that:

$h_{i,1}x_{1}+h_{i,2}x_{2}+\ldots+h_{i,n}x_{n}>c_{i}.$

Let $\Psi$ be a linear transformation applying all the half-space conditions:

$\displaystyle\Psi(x)=Hx+c=\begin{bmatrix}-h_{1,1}&-h_{1,2}&\ldots&-h_{1,n}\\\
-h_{2,1}&-h_{2,2}&\ldots&-h_{2,n}\\\ \ldots&&&\ldots\\\
-h_{k,1}&-h_{k,2}&\ldots&-h_{k,n}\end{bmatrix}\begin{bmatrix}x_{1}\\\ x_{2}\\\
\ldots\\\ x_{n}\end{bmatrix}+\begin{bmatrix}c_{1}\\\ c_{2}\\\ \ldots\\\
c_{k}\end{bmatrix},$

where $H$ is a $k\times n$ matrix. Entry-wise this matrix $\Psi(x)$ looks as
follows

$\Psi(x)_{i}=-h_{i,1}\cdot x_{1}-h_{i,2}\cdot x_{2}-\ldots-h_{i,n}\cdot
x_{n}+c_{i}.$

Notice that this implies that whenever $x\in H_{i}$ we have
$\text{ReLU}(\Psi(x))_{i}=0$. The first layer is given by:

$\chi^{(1)}=\text{ReLU}(W^{(1)}x+b^{(1)})=\text{ReLU}\left(\begin{bmatrix}I_{n}\\\
-I_{n}\\\ H\end{bmatrix}x+\begin{bmatrix}0\\\ 0\\\ c\end{bmatrix}\right),$

which is an activation vector of length $2\cdot n+k$.

This transformation develops the building blocks to generate neurons that are
only inactive when $x$ is in a certain region: we want to construct a layer
that only has an inactive neuron whenever the input is in a particular region.
In other words, we find a $p\times k$ zero-one matrix $R$ which describes the
regions in terms of which boundaries are active. Precisely, we can design $R$
so that $R\cdot\text{ReLU}(\Psi(x))$ has a zero entry at $j$ only when
$x\in\mathbb{\omega}_{j},j\in\\{1,\ldots,p\\}$. Assume without loss of
generality that the half-space conditions corresponding to region $\omega_{j}$
are $H_{1},\ldots,H_{a}$. The half-space conditions $H_{1},\ldots,H_{a}$ are
satisfied at a point $x$ if and only if $x\in\omega_{j}$. We construct $R$
such that at row $j$ it assigns a 1 to entries $1,\ldots,a$, and a 0 to all
other entries in that row, repeating this for all regions. This leads to the
description of the second layer:

$\displaystyle\chi^{(2)}=\text{ReLU}(W^{(2)}\chi^{(1)}+b^{(2)})$
$\displaystyle=\text{ReLU}\left(\begin{bmatrix}I_{n}&0&0\\\ 0&I_{n}&0\\\
0&0&R\end{bmatrix}\chi^{(1)}+\begin{bmatrix}0\\\ \vdots\\\
0\end{bmatrix}\right)$ $\displaystyle=\text{ReLU}\left(\begin{bmatrix}\hskip
12.0pt\text{ReLU}(x)\\\ \hskip 12.0pt\text{ReLU}(-x)\\\
R\cdot\text{ReLU}(\Psi(x))\end{bmatrix}\right),$

as an activation vector of length $2\cdot n+p$.

Finally, in the third layer we 1) multiply the input with each of the linear
models, and 2) use the indicator function that is zero only at entry $p$ if
the input $x$ is in part $p$, to isolate the correct linear model. Without
loss of generality, we assume that $m=1$ so that
$\mathcal{N}:\mathbb{R}^{n}\rightarrow\mathbb{R}$. If the dimension of the
output space $m>1$, then we repeat the construction of the last layer $m$
times.

Let $\Lambda$ be a linear transformation given by:

$\Lambda(x)=\alpha^{T}x+\beta,$

where $\alpha,\beta$ are respectively a $p\times n$ matrix and a
$p$-dimensional bias, such that the row $\alpha_{i}$ and entry $\beta_{i}$
contain the coefficients of $f_{i}$. Note that, in this step, if $m>1$, then
the matrix and vector would be $p\cdot m\times n$ and $p\cdot m$ dimensional
respectively.

We construct a matrix $O_{p}=\theta\cdot I_{p}$, where $\theta=\infty$, such
that $\infty\cdot 0=0$ and $\infty\cdot a=\infty$ for all
$a\in\mathbb{R}_{>0}$. Note that Python contains such a constant, denoted by
inf. We use this matrix so that when we subtract it from a matrix of linear
models, the only unaffected linear model will be $f_{j}$, i.e.

$\Lambda(x)-O_{p}\cdot\text{ReLU}(R\cdot\text{ReLU}(\Psi(x)))=\begin{bmatrix}-\infty\\\
\vdots\\\ -\infty\\\ \Lambda(x)_{j}\\\ -\infty\\\ \vdots\\\
-\infty\end{bmatrix},$

which is a vector of length $p$ for which the only positive entry is given by
the linear model at the region $j$ evaluated at $x$. Since elements of other
regions can lie arbitrarily close to region $\omega_{j}$, each
$R\cdot\text{ReLU}(\Psi(x))$ can be arbitrarily small, and so we cannot just
choose a very large number instead of infinity. This entails our third layer
activations are given by:

$\displaystyle\chi^{(3)}=\text{ReLU}(W^{(3)}\chi^{(2)}+b^{(3)})$
$\displaystyle=\text{ReLU}\left(\begin{bmatrix}\alpha&-\alpha&-O_{p}\\\
-\alpha&\alpha&-O_{p}\end{bmatrix}\chi^{(2)}+\begin{bmatrix}\beta\\\
-\beta\end{bmatrix}\right)$
$\displaystyle=\text{ReLU}\left(\begin{bmatrix}\alpha&-\alpha&-O_{p}\\\
-\alpha&\alpha&-O_{p}\end{bmatrix}\begin{bmatrix}\hskip
12.0pt\text{ReLU}(x)\\\ \hskip 12.0pt\text{ReLU}(-x)\\\
R\cdot\text{ReLU}(\Psi(x))\end{bmatrix}+\begin{bmatrix}\beta\\\
-\beta\end{bmatrix}\right)$
$\displaystyle=\text{ReLU}\left(\begin{bmatrix}\hskip 3.5pt\Lambda(x)\hskip
4.0pt-O_{p}\cdot\text{ReLU}\left(R\cdot\text{ReLU}(\Psi(x))\right)\\\
-\Lambda(x)-O_{p}\cdot\text{ReLU}\left(R\cdot\text{ReLU}(\Psi(x))\right)\end{bmatrix}\right)$

which is a vector of length $2p$ with exactly one non-zero entry at either $j$
or $2j$. This non-zero entry is $\Lambda(x)$ at row $j$ (if $\Lambda(x)$ is
positive) or $-\Lambda(x)$ at row $2j$ (if $\Lambda(x)$ is negative).

Lastly we need a weight matrix to project onto $\mathbb{R}^{m}$. This
projection requires $2p$ weights. When we project the $-\Lambda(x)$ value to
the output layer, we need to swap the sign. The first $p$ weights of $W^{(4)}$
are 1 and the last $p$ weights are $-1$:

$\mathcal{S}(x)=W^{(4)}\cdot\chi^{(3)}=\Lambda(x)_{j}=\mathcal{N}(x).$

Note that here we assumed $m=1$. In general, the length of $\chi^{(3)}$ is
$2\cdot p\cdot m$, as is the number of required projection weights. ∎

######  Corollary 1.

Given a ReLU network
$\mathcal{N}\colon\mathbb{R}^{n}\rightarrow\mathbb{R}^{m}$, the shallow
network $\mathcal{S}\colon\mathbb{R}^{n}\rightarrow\mathbb{R}^{m}$ of depth
$L=3$, as specified in the proof of Theorem 1, has width bounded by

$\max\\{2n+k,2n+p,2\cdot p\cdot m\\},$

where $p=\\#\Omega$ and $k=\\#\\{\text{half space conditions}\\}$.

Note that Montufar et al. (2014), Serra & Ramalingam (2020), and Chen et al.
(2022), find progressively tighter bounds for the number of linear regions in
ReLU networks as functions of the number of neurons at each layer.

######  Corollary 2.

For every continuous piece-wise linear function $f$, there exists a shallow
neural network $\mathcal{S}$ of depth $L=3$ with weights in the extended reals
$\bar{\mathbb{R}}=\mathbb{R}\cup\\{\infty\\}$ such that for all
$x\in\mathbb{R}^{n}$ a compact subspace of $\mathbb{R}^{n}$, the functions are
identical.

###### Proof.

He et al. (2021) proves that every piece-wise linear function on a compact
subspace of real space can be represented exactly by a neural network of
finite depth and width. ∎

######  Corollary 3.

For every tensor convolutional neural network (including all graph
convolutional neural networks, recurrent neural networks and convolutional
neural networks) with ReLU activation functions there exists a shallow neural
network $\mathcal{S}$ of depth $L=3$ with weights in the extended reals
$\bar{\mathbb{R}}=\mathbb{R}\cup\\{\infty\\}$ such that for all
$x\in\mathbb{R}^{n}$, the functions are identical.

###### Proof.

Villani & McBurney (2023) show that tensor convolutional networks with ReLU
activations can be decomposed into local linear models (like feedforward ReLU
networks). ∎

This theory allows us to verify whether two networks are functionally
identical on their domain of definition, rather than just on their test
dataset. By lexicographically orderering the linear models and half-space
conditions, the algorithm maps any set of functionally identical networks to
the same unique shallow network.

##  4 Implementation

Given a deep ReLU network, we propose an algorithm that finds the weights of a
functionally identical shallow network. This algorithm is based on the
constructive proof of Theorem 1. We show that every activation pattern leads
to a linear program, whose feasible set is exactly a region of the partition
of a ReLU network.

In order to find the weights of the shallow network, we need to search the
space of activation patterns to find all the activation patterns that yield a
nonempty region. This is a vast space, with $2^{n_{1}+\ldots+n_{L}}$ possible
patterns, which we reduce through certain heuristics. We develop a theory that
connects linear programs to ReLU networks, and search the reduced space of
patterns via a brute force algorithm.

###  4.1 Formal Correspondence between Linear Programs and Regions

We define local linear programs as the set of constraints required by an
activation pattern at a given layer.

######  Definition 3 (Local linear program).

Let $P=\\{P^{(1)},\ldots,P^{(L)}\\}$ be an activation pattern. The local
linear program corresponding to $P^{(l)}$, is given by the set of activation
vectors $\chi^{(l-1)}$ at layer $(l-1)$ such that

$\left(\mathrm{diag}(\mathbf{1}-P^{(l)})\cdot
W^{(l)}-\mathrm{diag}(P^{(l)})\cdot
W^{(l)}\right)\cdot\chi^{(l-1)}\leq-\mathrm{diag}(\mathbf{1}-P^{(l)})\cdot
b^{(l)}+\mathrm{diag}(P^{(l)})\cdot b^{(l)}.$

The following lemma is used in the proof of Lemma 2 and Proposition 2.

######  Lemma 1.

Let $x\in\mathbb{R}^{n}$, $x$ has activation pattern $P^{(l)}$ at layer $l$
only if $\chi^{(l-1)}$ satisfies the local linear program corresponding to
$P^{(l)}$. (See Appendix.)

We use the following lemma to reduce the search space of possible patterns.

######  Lemma 2.

Let $P=\\{P^{(1)},\ldots,P^{(l)},\ldots,P^{(L)}\\}$ be the activation pattern
of $\omega_{P}$. If the corresponding local linear program at layer $l$ has an
empty feasible set, then $\omega_{P}=\emptyset$. (See Appendix.)

We define global linear programs in terms of the input vector as opposed to in
terms of an activation vector.

######  Definition 4 (Global linear program).

Let $P=\\{P^{(1)},\ldots,P^{(L)}\\}$ be an activation pattern. Recursively
define

$\displaystyle A^{(1)}$ $\displaystyle:=W^{(1)}$ $\displaystyle A^{(l)}$
$\displaystyle:=W^{(l)}\cdot\mathrm{diag}(P^{(l-1)})\cdot A^{(l-1)}$
$\displaystyle d^{(1)}$ $\displaystyle:=b^{(1)}$ $\displaystyle d^{(l)}$
$\displaystyle:=\cdot W^{(l)}\cdot\mathrm{diag}(P^{(l-1)})\cdot
d^{(l-1)}+b^{(l)}.$

The global linear program corresponding to $P$ at layer $l$, is given by the
set of inputs $x\in\mathbb{R}^{n}$ such that for all $1\leq l\leq L$ we have

$\left(\mathrm{diag}(\mathbf{1}-P^{(l)})\cdot
A^{(l)}-\mathrm{diag}(P^{(l)})\cdot A^{(l)}\right)\cdot
x\leq-\mathrm{diag}(\mathbf{1}-P^{(l)})\cdot
d^{(l)}+\mathrm{diag}(P^{(l)})\cdot d^{(l)}.$

The following proposition is used in the algorithm to find the parameters of
the hyperplanes as the constraints of the global linear program.

######  Proposition 2.

If $x\in\mathbb{R}^{n}$ has activation pattern
$P=\\{P^{(1)},\ldots,P^{(L)}\\}$, then $x$ satisfies the global linear program
corresponding to $P$. (See Appendix.)

###  4.2 Algorithm

It is sufficient to find $H,c,\alpha,\beta$ to build the shallow network,
while knowing which half spaces are needed to define each region. The
algorithm we present to find the weights is structured as follows. First, we
identify the set of feasible patterns. For each of these, we compute the
parameters $A^{(l)},d^{(l)}\forall l\in[L]$ of the global linear program.
Stacking these matrices determines the half-space conditions for each
activation pattern, and hence $-H=\texttt{stack}(\\{A^{(l)}\\}_{l\in[L]})$ and
similarly for $c=\texttt{stack}(\\{d^{(l)}\\}_{l\in[L]})$. Finally, given the
model weights and an activation pattern, it is easy to compute the local
linear model $\alpha,\beta$ by using the explicit formula from Sudjianto et
al. (2020).

Algorithm 1 Find Shallow Network Weights

0: $L>0,\forall l\in[L],n_{i}>0,W^{(l)}\in\mathbb{R}^{n_{l}\times
n_{l+1}},b^{(l)}\in\mathbb{R}^{n_{l+1}}$ {this is the input}

0: $\alpha,\beta,H,c$ {this is the output}

1: $\forall l\text{ initialise lists called }\texttt{layerwise-feasible-
patterns}_{l}$

2: for $l\in[L]$ do

3: for $P^{(l)}\in\\{0,1\\}^{n_{l}}$ do

4: if $\texttt{has-nonempty-local-linear-
program}(P^{(l)},W^{(l)},b^{(l)})=\text{True}$ then

5: store $P^{(l)}$ in $\texttt{layerwise-feasible-patterns}_{l}$

6: Initialise lists of lists called feasible-patterns, all-hyperplanes

7: $\text{store }\texttt{layerwise-feasible-patterns}_{1}\text{ in }\texttt{
feasible-patterns }$

8: for $l\in\\{2,...,L\\}$ do

9: for $P^{(l)}\text{ in }\texttt{layerwise-feasible-patterns}_{l}$ do

10: for pattern in feasible-patterns do

11: $A^{(l)},d^{(l)}\leftarrow\texttt{get-linear-program-
weights}(P^{(l)},\\{W^{(i)},b^{(i)}\\}_{i\in[l]})$

12: if $\texttt{has-nonempty-global-linear-
program}(P^{(l)},\\{A^{(i)},d^{(i)}\\}_{i\in[l]})=\text{True}$ then

13: $\text{store }P^{(l)}\text{ in }\texttt{pattern}$

14: store pattern in feasible-patterns

15: $\text{store }A^{(l)},d^{(l)}\text{ in }\texttt{pattern}$

16: $H,c\leftarrow\texttt{get-hyperplanes}(\\{A^{(i)},d^{(i)}\\}_{i\in[l]})$

17: $\text{store }H,c\text{ in }\texttt{hyperplanes}$

18: for $P\leftarrow\texttt{pattern}\text{ in }\texttt{feasible-patterns}$ do

19: $\alpha_{P},\beta_{P}\leftarrow\texttt{get-local-linear-
model}(P,\\{W^{(l)},b^{(l)})\\}_{l\in[L]})$

20: store $\alpha_{P},\beta_{P}$ in local-linear-models

21: return local-linear-models, hyperplanes

While the algorithm has complexity $\mathcal{O}(2^{\Sigma_{l=1}^{L}n_{l}})$,
Hanin & Rolnick (2019) find that the number of activation patterns is
generally small. Our algorithm avoids searching the entire pattern space by
pruning large portions of it.

Figure 3: We plot the time to compute the shallow networks corresponding to
randomly initialized networks $\mathcal{N}$ on the z-axis as a function of the
number of neurons in the first hidden layer (y-axis) and the second hidden
layer (x-axis) of $\mathcal{N}$. Error bars indicate one standard deviation.

We executed the algorithm on a local machine’s CPU (16 GB RAM). We randomly
initialized weights on a small network (using Xavier uniform). The networks
have three hidden layers, with variable first and second layer width and a
fixed third layer width. We measure the time it takes to compute a shallow
network for each of the randomly initialized networks. For each combination of
layer widths we repeat the experiment five times.

The time taken to compute the algorithm for randomly initialized networks
grows exponentially with the number of neurons, see Figure 3. Note that the
initialisation forces the algorithm to work in the worst case, where none of
the activation patterns can be pruned and all patterns need to be checked. As
expected based on the algorithm’s design, the time grows faster in the number
of second layer nodes than in first layer nodes. In Figure 3, we see that 6
neurons in the first layer, but only 5 neurons in the second layer requires
slightly less than 100 seconds to compute, whereas the reverse takes slightly
more than 100 seconds on average.

##  5 Interpretability

The finding that any ReLU Network can be decomposed into a set of local linear
models (Sudjianto et al., 2020) has made black-box neural networks more
interpretable. Very recently, an algorithm was introduced Balestriero & LeCun
(2023) that (like our algorithm) provides a global interpretation of the model
by specifying the partition and the linear model of each part.

The fully understood construction of the white-box shallow network empowers
users to perform model surgery on it. Below, we highlight two ways in which
interpretability is enhanced: (1) we can compute fast SHAP values for each
datapoint; (2) given a region, we give an explanation for the region by
approximating it with a hypercube containing it.

###  5.1 Calculating Exact SHAP Values

SHAP values are popular metrics used as explanations in the field of
explainable artificial intelligence (Lundberg & Lee, n.d.; Samek et al.,
2021). For a given datapoint they impute how much each input dimension
contributes to the output. SHAP values are defined as follows.

######  Definition 5 (SHAP values).

Given a function $f\colon\mathbb{R}^{n}\rightarrow\mathbb{R}^{m}$ and an input
$x\in\mathbb{R}^{n}$. A function
$f_{x}\colon\\{0,1\\}^{n}\rightarrow\mathbb{R}^{m}$ is a _masking function_ if
it evaluates $f(x)$ with $x$ unchanged when $z_{i}=1$ and evaluates a ‘turned
off’ input at dimension $i$ (such as mean or zero) when the input $z_{i}=0$,
for all $i\in[n]$. The _SHAP values_ for each feature (or dimension) $i\in[n]$
are given by an $n\times m$ matrix. Let
$f_{x}\colon\\{0,1\\}^{n}\rightarrow\mathbb{R}^{m}$ be a masking function. The
SHAP values are then:

$\phi_{i}(f,x)=\sum_{z\in\\{z^{\prime}\in\\{0,1\\}^{n}\colon
z^{\prime}_{i}=1\\}}\frac{|z|!(n-|z|-1)!}{n!}[f_{x}(z)-f_{x}(z_{-i})],$

where $(z_{-i})_{j}:=z_{j}$ for all $j$ excluding $i$; and $|z|$ counts the
number of nonzero entries of $z$.

Typically, for machine learning models, these SHAP values are estimated.
However, for a linear model they are known (Lundberg & Lee, n.d.) and are
given in terms of the mean of a distribution over the input space. Hence,
given a decomposition of a network we can give exact SHAP values.

######  Proposition 3.

Let $\mathcal{N}\colon\mathbb{R}^{n}\rightarrow\mathbb{R}^{m}$ be a ReLU
network with decomposition into local linear models. Let $\omega$ be a region
with local linear model $f(x^{\prime})=\alpha x^{\prime}+\beta$, let $D$ be a
distribution over $\omega$ and let $x\in\omega$. Let $f_{x}$ be a masking
function, where given a masked dimension we define $f_{x}$ as returning a
sample from the distribution $D$. Then the SHAP values for feature $i$ are
given by

$\phi_{i}(\mathcal{N},x)=\alpha(x-\mathbb{E}_{D(\omega)}(x)).$

###### Proof.

Since $\mathcal{N}$ is linear on the polytope $\omega$, for every sampled
input $X\sim D(\omega)$ we will have that $\mathcal{N}(X)=f_{x}(X)=\alpha
X+\beta$. The result then follows from Lundberg & Lee (n.d.). ∎

A consequence of this proposition is that SHAP values can be computed exactly
and almost instantly from the decomposition after computing the mean of the
background distribution. 111This can be done analytically if we choose the
distribution to be uniform. However, it may be inappropriate to select this
distribution, since the polytope may not be bounded.

###  5.2 Explainability via Hypercubes around Regions

Given a region, we can approximate it by drawing the smallest possible
hypercube around it. This enables us to summarise the region, using a small
number of parameters: the location and size of the hypercube. In particular,
we highlight that this summary is in tension with faithfully representing the
region, which would require specifying many hyperplanes and $n$ parameters for
each one of these hyperplanes.

We trained a feedforward ReLU network with neuron vector [5,7,4] on the first
two dimensions of the Iris dataset (Fisher, 1936) for 5000 epochs with a
Sigmoid output layer, cross entropy loss and Adam with learning rate 0.0001
and betas equal to 0.9 and 0.999. We then used our algorithm, as introduced in
Section 4.2 to decompose the neural network and find all regions. We then
select the regions where test data lives and record them in Figure 4.

Figure 4: We plot the regions (in green) for a test portion (40%) of the first
two dimensions of the Iris dataset. All these datapoints (red crosses) fall in
one of five regions. In red we draw the smallest hypercube that fits the
entire region. The x-axis represents petal length, and the y-axis petal width.

The hypercubes are coarse explanations that become less faithful as the number
of dimensions increases. However, identifying the position as well as
inspecting which inputs are in a region helps us identify common
characteristics of the inputs; the size parameter of the cube can be compared
to others in order to capture an approximation of the size of the region.

##  6 Discussion

Our contribution has been to prove all deep ReLU networks can be rewritten as
a shallow network (Theorem 1), while providing a way to compute the weights
algorithmically (Algorithm 1). This enhances interpretability by allowing us
to quickly compute feature importance and giving details of the exact, local
functional relationship between input and output. Deep neural networks discern
hierarchical concepts, with later layers encapsulating more complex concepts
than earlier ones. Remarkably, we demonstrate that these concepts can be
rearranged horizontally, maintaining their original functionality. This
restructuring allows us to derive a shallow network from a deep one.

Our construction of a shallow network is not injective, in that multiple
(functionally identical) deep networks with different architectures can all
map to the same shallow network. If we consider equivalence classes of neural
networks that each encode a different function, then our shallow networks can
be seen as a representative of their equivalence class.

###  6.1 Limitations

The construction of a shallow network makes use of infinite weights. Although
these weights can be implemented in Python, they can not be fine-tuned using
gradient descent. Note that the weights encoding the linear models can be
fine-tuned. To maintain the transparent network structure after fine-tuning,
the weights encoding identity matrices between the blue blocks in Figure 2
should be frozen. Additionally, the four weight matrices denoted by $\alpha$
and $-\alpha$ between the blue and green blocks should be updated in
conjunction with one another.

The current algorithm is well suited for small models, but large computational
resources are needed to perform the search of feasible patterns in larger
models. Future work should focus on finding efficient heuristics to prune the
space of possible activation patterns. Moreover, research should prioritise
developing faithful explanations that navigate the complexity of these models.

## References

  * (1)
  * Balestriero & LeCun (2023) Balestriero, R. & LeCun, Y. (2023), Fast and exact enumeration of deep networks partitions regions, in ‘ICASSP 2023-2023 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)’, IEEE, pp. 1–5.
  * Chen et al. (2022) Chen, K.-L., Garudadri, H. & Rao, B. D. (2022), ‘Improved Bounds on Neural Complexity for Representing Piecewise Linear Functions’, 36(NeurIPS).
  * Dong et al. (2021) Dong, H., Liu, B., Chen, F., Ye, D. & Liu, G. (2021), ‘How to explain neural networks: an approximation perspective’, arXiv preprint arXiv:2105.07831 .
  * Fisher (1936) Fisher, R. A. (1936), ‘The use of multiple measurements in taxonomic problems’, Annals of Eugenics 7(2), 179–188.
  * Hanin & Rolnick (2019) Hanin, B. & Rolnick, D. (2019), ‘Deep ReLU networks have surprisingly few activation patterns’, Advances in Neural Information Processing Systems 32(NeurIPS).
  * He et al. (2021) He, J., Li, L. & Xu, J. (2021), ‘ReLU Deep Neural Networks from the Hierarchical Basis Perspective’, pp. 1–27.
  * Jiang et al. (2022) Jiang, Z., Wang, Y., Li, C.-T., Angelov, P. & Jiang, R. (2022), ‘Delve into Activations: Towards Understanding Dying Neuron’, IEEE Transactions on Artificial Intelligence pp. 1–13.
  * Lundberg & Lee (n.d.) Lundberg, S. M. & Lee, S.-I. (n.d.), ‘A unified approach to interpreting model predictions’, Advances in Neural Information Processing Systems 30(NeurIPS).
  * Montufar et al. (2014) Montufar, G. F., Pascanu, R., Cho, K. & Bengio, Y. (2014), ‘On the number of linear regions of deep neural networks’, Advances in Neural Information Processing Systems 27(NeurIPS).
  * Samek et al. (2021) Samek, W., Montavon, G., Lapuschkin, S., Anders, C. J. & Müller, K. R. (2021), ‘Explaining Deep Neural Networks and Beyond: A Review of Methods and Applications’, Proceedings of the IEEE 109(3), 247–278.
  * Serra & Ramalingam (2020) Serra, T. & Ramalingam, S. (2020), ‘Empirical bounds on linear regions of deep rectifier networks’, AAAI 2020 - 34th AAAI Conference on Artificial Intelligence pp. 5628–5635.
  * Sudjianto et al. (2020) Sudjianto, A., Knauth, W., Singh, R., Yang, Z. & Zhang, A. (2020), ‘Unwrapping the black box of deep relu networks: interpretability, diagnostics, and simplification’, arXiv preprint arXiv:2011.04041 .
  * Villani & McBurney (2023) Villani, M. J. & McBurney, P. (2023), ‘Unwrapping all relu networks’, arXiv preprint arXiv:2305.09424 .

## Appendix

###  7.1 Proofs supporting Section 4

######  Definition 6 (Local linear program).

Let $P=\\{P^{(1)},\ldots,P^{(L)}\\}$ be an activation pattern. The local
linear program corresponding to $P^{(l)}$, is given by the set of activation
vectors $\chi^{(l-1)}$ at layer $(l-1)$ such that

$\left(\mathrm{diag}(\mathbf{1}-P^{(l)})\cdot
W^{(l)}-\mathrm{diag}(P^{(l)})\cdot
W^{(l)}\right)\cdot\chi^{(l-1)}\leq-\mathrm{diag}(\mathbf{1}-P^{(l)})\cdot
b^{(l)}+\mathrm{diag}(P^{(l)})\cdot b^{(l)}.$

######  Lemma 3.

Let $x\in\mathbb{R}^{n}$; $x$ has activation pattern $P^{(l)}$ at layer $l$
only if $\chi^{(l-1)}$ satisfies the local linear program corresponding to
$P^{(l)}$.

###### Proof.

Suppose $x\in\mathbb{R}^{n}$ has activation pattern $P^{(l)}$.
If $P^{(l)}_{i}=0$ then $(W^{(l)}\chi^{(l-1)}(x)+b^{(l)})_{i}\leq 0$ then
$(W^{(l)}\chi^{(l-1)}(x))_{i}\leq-b^{(l)}_{i}$, so

$\mathrm{diag}(\mathbf{1}-P^{(l)})\cdot
W^{(l)}\cdot\chi^{(l-1)}(x)\leq-\mathrm{diag}(\mathbf{1}-P^{(l)})\cdot
b^{(l)}.$

If $P^{(l)}_{i}=1$ then $(W^{(l)}\chi^{(l-1)}(x)+b^{(l)})_{i}\geq 0$ then
$-(W^{(l)}\chi^{(l-1)}(x))_{i}\leq b^{(l)}_{i}$, so

$-\mathrm{diag}(P^{(l)})\cdot
W^{(l)}\cdot\chi^{(l-1)}(x)\leq\mathrm{diag}(P^{(l)})\cdot b^{(l)}.$

We can conclude that

$\left(\mathrm{diag}(\mathbf{1}-P^{(l)})\cdot
W^{(l)}-\mathrm{diag}(P^{(l)})\cdot
W^{(l)}\right)\cdot\chi^{(l-1)}(x)\leq-\mathrm{diag}(\mathbf{1}-P^{(l)})\cdot
b^{(l)}+\mathrm{diag}(P^{(l)})\cdot b^{(l)}.$

∎

######  Lemma 4.

Let $P=\\{P^{(1)},...,P^{(l)},...,P^{(L)}\\}$ be the activation pattern of
$\omega_{P}$. If the corresponding local linear program at layer $l$ has an
empty feasible set, then $\omega_{P}=\emptyset$.

###### Proof.

We will prove this lemma by contradiction. Assume that the local linear
program at layer $l$ has an empty feasible set and that $w_{P}\neq\emptyset$.

Let $x\in\omega_{P}$. Then $x$ has activation pattern $P^{(l)}$. By Lemma 3
this means that $x$ satisfies

$\left(\mathrm{diag}(\mathbf{1}-P^{(l)})\cdot
W^{(l)}-\mathrm{diag}(P^{(l)})\cdot
W^{(l)}\right)\cdot\chi^{(l-1)}(x)\leq-\mathrm{diag}(\mathbf{1}-P^{(l)})\cdot
b^{(l)}+\mathrm{diag}(P^{(l)})\cdot b^{(l)}.$

However, in this case the local linear program at layer $l$ has non-empty set,
so we have found a contradiction. ∎

######  Definition 7 (Global linear program).

Let $P=\\{P^{(1)},\ldots,P^{(L)}\\}$ be an activation pattern. Recursively
define

$\displaystyle A^{(1)}$ $\displaystyle:=W^{(1)}$ $\displaystyle A^{(l)}$
$\displaystyle:=W^{(l)}\cdot\mathrm{diag}(P^{(l-1)})\cdot A^{(l-1)}$
$\displaystyle d^{(1)}$ $\displaystyle:=b^{(1)}$ $\displaystyle d^{(l)}$
$\displaystyle:=\cdot W^{(l)}\cdot\mathrm{diag}(P^{(l-1)})\cdot
d^{(l-1)}+b^{(l)}.$

The global linear program corresponding to $P$ at layer $l$, is given by the
set of inputs $x\in\mathbb{R}^{n}$ such that for all $1\leq l\leq L$ we have

$\left(\mathrm{diag}(\mathbf{1}-P^{(l)})\cdot
A^{(l)}-\mathrm{diag}(P^{(l)})\cdot A^{(l)}\right)\cdot
x\leq-\mathrm{diag}(\mathbf{1}-P^{(l)})\cdot
d^{(l)}+\mathrm{diag}(P^{(l)})\cdot d^{(l)}.$

######  Proposition 4.

If $x\in\mathbb{R}^{n}$ has activation pattern
$P=\\{P^{(1)},\ldots,P^{(L)}\\}$, then $x$ satisfies the global linear program
corresponding to $P$.

###### Proof.

By definition of $P^{(l)}$ we have that,
$\chi^{(l)}=\mathrm{diag}(P^{(l)})\cdot(W^{(l)}\chi^{(l-1)}+b^{(l)})$ for
$x\in\omega_{P}$. We will prove by induction that

$\chi^{(l)}=\mathrm{diag}(P^{(l)})\left(A^{(l)}x+d^{(l)}\right),\forall
x\in\omega_{P}.$

The base case is true by definition:

$\chi^{(1)}=\mathrm{diag}(P^{(1)})\cdot\left(A^{(1)}x+d^{(1)}\right)=\mathrm{diag}(P^{(1)})\cdot\left(W^{(1)}x+b^{(1)}\right).$

Now assuming that
$\chi^{(l-1)}=\mathrm{diag}(P^{(l-1)})\left(A^{(l-1)}x+d^{(l-1)}\right)$ we
will show that
$\chi^{(l)}=\mathrm{diag}(P^{(l)})\left(A^{(l)}x+d^{(l)}\right)$. We write

$\displaystyle\chi^{(l)}$
$\displaystyle=\mathrm{diag}(P^{(l)})\left(W^{(l)}\chi^{(l-1)}+b^{(l)}\right)$
$\displaystyle=\mathrm{diag}(P^{(l)})\left(W^{(l)}\left(A^{(l-1)}x+d^{(l-1)}\right)+b^{(l)}\right)$
$\displaystyle=\mathrm{diag}(P^{(l)})\left(W^{(l)}A^{(l-1)}x+W^{(l)}d^{(l-1)}+b^{(l)}\right)$
$\displaystyle=\mathrm{diag}(P^{(l)})\left(A^{(l)}x+d^{(l)}\right).$

By Lemma 3, for all $l$, $\chi^{(l-1)}$ satisfy the local linear program, or
equivalently all $\mathrm{diag}(P^{(l-1)})\left(A^{(l-1)}x+d^{(l-1)}\right)$
satisfy the linear program if $x\in\omega_{P}$. We rewrite the local linear
programs as:

$\displaystyle\left(\mathrm{diag}(\mathbf{1}-P^{(l)})\cdot
W^{(l)}-\mathrm{diag}(P^{(l)})\cdot
W^{(l)}\right)\mathrm{diag}(P^{(l-1)})\left(A^{(l-1)}x+d^{(l-1)}\right)$
$\displaystyle\leq-\mathrm{diag}(\mathbf{1}-P^{(l)})\cdot
b^{(l)}+\mathrm{diag}(P^{(l)})\cdot b^{(l)}.$

From which we conclude that,

$\displaystyle\left(\mathrm{diag}(\mathbf{1}-P^{(l)})\cdot
W^{(l)}-\mathrm{diag}(P^{(l)})\cdot
W^{(l)}\right)\mathrm{diag}(P^{(l-1)})A^{(l-1)}x$
$\displaystyle\leq-\mathrm{diag}(\mathbf{1}-P^{(l)})\cdot(b^{(l)}+W^{(l-1)}\mathrm{diag}(P^{(l-1})d^{(l-1)})+\mathrm{diag}(P^{(l)})\cdot(b^{(l)}+W^{(l-1)}\mathrm{diag}(P^{(l-1)})d^{(l-1)}),$

simplifying to:

$\displaystyle\left(\mathrm{diag}(\mathbf{1}-P^{(l)})\cdot
A^{(l)}-\mathrm{diag}(P^{(l)})\cdot
A^{(l)}\right)x\leq-\mathrm{diag}(\mathbf{1}-P^{(l)})\cdot
d^{(l)}+\mathrm{diag}(P^{(l)})\cdot d^{(l)},$

as required. ∎