How to uniquely associate a directed graph with a feedforward neural network?

Question

I want to write an algorithm that returns a unique directed graph (an adjacency matrix) that represents the structure of a given feedforward neural network (FNN). My idea is to deconstruct the FNN into the input vector and some nodes (see definition below), and then draw those as vertices, but I do not know how to do so in a unique way.

Question: Is it possible to construct such an algorithm, and if so, how would you formalize it?

---

Example [Shallow Feedforward Neural Network (SNN)]

To illustrate the problem, consider an SNN, defined as a mapping $f=\left(f_1(\mathbf{x}), \ldots, f_m(\mathbf{x})\right): \mathbb{R}^n\rightarrow\mathbb{R}^m$ where for $k=1,\ldots,m$

\begin{align} f_k(\mathbf{x}) &= \sum_{j=1}^{\ell} w_{j,k}^{(2)} \rho \left( \sum_{i=1}^n w_{i,j}^{(1)} x_i + w_{0,j}^{(1)} \right) + w_{0,k}^{(2)}, \quad \mathbf{x}=(x_1,\ldots,x_n)\in\mathbb{R}^n \end{align} and $w_{i,j}^{(k)}\in\mathbb{R}$ is fixed for all $i,j,k \in \mathbb{N}$ and $\rho:\mathbb{R}\rightarrow\mathbb{R}$ is a continuous mapping.

I want to determine the nodes that make up the FNN, where a node $N^{\rho}: \mathbb{R}^n\rightarrow\mathbb{R}$ is defined as a mapping \begin{align} \label{eq:node} && \quad && N^{\rho}(\mathbf{x}) &= \rho\left(\sum_{i=1}^n w_i x_i + w_0 \right), & \mathbf{x}=(x_1,\ldots,x_n)\in\mathbb{R}^n \end{align} where $\mathbf{w}=(w_0, \ldots,w_n)\in\mathbb{R}^{n+1}$ is fixed.

Clearly (to me) I can write each $f_k$ as

\begin{align} f_k(\mathbf{x}) &= \sum_{j=1}^{\ell} w_{j,k}^{(2)} N^{\rho}_j(\mathbf{x}) + w_{0,k}^{(2)}, \end{align} where $N^{\rho}_{j}$ is a node for $j=1,\ldots,\ell$. Now I see that $f_k$ is a node which takes as input the output of other nodes. But how can I formalise this in an algorithm? And does it generalize to Deep Feedforward Neural Networks?

Answer 1

I think you can do this in multiple ways.

The easiest algorithm that comes to my mind right now produces a sparse (which is also some kind of block matrix) $N \times N$ adjacency matrix for a typical MLP/FFN with a total of $N$ neurons (including input and output neurons), where each neuron $n_l^k$ at layer $l$ has a directed edge that goes into all neurons at layer $l+1$.

This is the algorithm.

1. Create an $N \times N$ matrix $G \in \{0, 1\}^{N \times N}$ with zeros

   • Comment 1: $G_{ij}$ is the element of the matrix at row $i$ and column $j$.

   • Comment 2: Indices $i$ and $j$ start at $1$ and end at $N$

   • Comment 3: if we set $G_{ij} = 1$, then there's a directed edge from neuron $i$ to neuron $j$ (but not necessarily vice-versa: for that to be true, we would also need $G_{ji} = 1$)

   • Comment 4: we need to create a mapping between the indices $i$ and $j$ and the neurons in the neural network; this is done below!

2. Let $c(l)$ be the number of neurons at layer $l$

3. For each layer $l = 0, \dots, L - 1$

   • Comment 5: $l = 0$ is the input layer and $L$ is the output layer
   2. For $k=1, \dots, c(l)$
      • Comment 6: for example, $n_l^k = n_2^3$ is the third neuron at the first hidden layer
      1. Let $M = \sum_{h=0}^{l-1} c(h)$
         • Comment 7: $M$ is the number of neurons processed so far in the previous layers (excluding the neurons in the current layer)
      2. $i = k + M$
      3. For $t = 1, \dots, c(l+1)$
         1. $j = t + c(l) + M$
            • $j$ is basically the index of the graph $G$ that corresponds to the neuron $t$ in the next layer $l+1$
         2. Set $G_{ij} = 1$

4. Return the matrix $G$

The time complexity of this algorithm should roughly be $\mathcal{O}(L* {\max_l c(l)}^2)$. So, for example, for a neural network with 3 layers, 2 inputs, 5 hidden neurons, and 2 outputs, what would be the number of operations?