0
$\begingroup$

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?

$\endgroup$
4
  • $\begingroup$ I'm not sure what you're asking here. You say the output of the algorithm should be a graph, while the inputs are FNNs. But isn't a neural network already a graph? Do you want the algorithm to produce, for example, an adjacency matrix? $\endgroup$
    – nbro
    Dec 15 '21 at 13:19
  • $\begingroup$ The input should be a function (specifically an FNN) and the output should be a set of vertices and edges. My problem is that I informally consider neural networks as graphs, but in my project, I have defined neural networks as a class of functions. Now I want to formally associate a graph with a given neural network. $\endgroup$ Dec 15 '21 at 13:34
  • $\begingroup$ What should the edges be? Should they just represent the connectivity? So, are you effectively looking for an adjacency matrix that represents the neural network's connectivity between the neurons? Or maybe the edges should have weights? If yes, which ones? $\endgroup$
    – nbro
    Dec 15 '21 at 13:38
  • $\begingroup$ Exactly, the edges should just represent connectivity, so an adjacency matrix is sufficient. $\endgroup$ Dec 15 '21 at 13:39
0
$\begingroup$

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
    1. 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?

$\endgroup$
3
  • $\begingroup$ Ah, I see the idea! To directly associate the FFN $f$ with the graph, I would probably not count the neurons (since they do not appear in the formulation of $f$) but instead, count the non-zero weights (since I only want to draw edges if the weights are non-zero). Perhaps my problem formulation was unclear. To answer your question, I guess the number of operations would be 20 (not counting the calculation of $M$, $i$, and $j$). $\endgroup$ Dec 15 '21 at 16:42
  • $\begingroup$ The algorithm above can also be applied to the case of non-zero weights (although note that maybe you will not have many exactly zero weights, with real-valued weights). Rather than setting $G_{ij}=1$ in all cases, you also check the weight of the connection. Of course, as you said, the number of neurons may not be in the formulation of the neural network, but this information should be retrievable from the implementation of the layers. $\endgroup$
    – nbro
    Dec 15 '21 at 16:48
  • $\begingroup$ Exactly, it is just minor adjustments. Regarding the note on non-zero weights: To clarify, I am writing a theoretical project on neural networks, so it does not matter if they are exactly zero. Thanks for the algorithm! $\endgroup$ Dec 15 '21 at 16:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.