Answers.Body: <p>I think you can do this in multiple ways.</p>
  <p>The easiest algorithm that comes to my mind right now produces a sparse (which is also some kind of block matrix) <span class="math-container">$N \times N$</span> adjacency matrix for a typical MLP/FFN with a total of <span class="math-container">$N$</span> neurons (including input and output neurons), where each neuron <span class="math-container">$n_l^k$</span> at layer <span class="math-container">$l$</span> has a directed edge that goes into all neurons at layer <span class="math-container">$l+1$</span>.</p>
  <p>This is the algorithm.</p>
  <ol>
  <li><p>Create an <span class="math-container">$N \times N$</span> matrix <span class="math-container">$G \in \{0, 1\}^{N \times N}$</span> with zeros</p>
  <ul>
  <li><p>Comment 1: <span class="math-container">$G_{ij}$</span> is the element of the matrix at row <span class="math-container">$i$</span> and column <span class="math-container">$j$</span>.</p>
  </li>
  <li><p>Comment 2: Indices <span class="math-container">$i$</span> and <span class="math-container">$j$</span> start at <span class="math-container">$1$</span> and end at <span class="math-container">$N$</span></p>
  </li>
  <li><p>Comment 3: if we set <span class="math-container">$G_{ij} = 1$</span>, then there's a directed edge from neuron <span class="math-container">$i$</span> to neuron <span class="math-container">$j$</span> (but not necessarily vice-versa: for that to be true, we would also need <span class="math-container">$G_{ji} = 1$</span>)</p>
  </li>
  <li><p>Comment 4: we need to create a mapping between the indices <span class="math-container">$i$</span> and <span class="math-container">$j$</span> and the neurons in the neural network; this is done below!</p>
  </li>
  </ul>
  </li>
  <li><p>Let <span class="math-container">$c(l)$</span> be the number of neurons at layer <span class="math-container">$l$</span></p>
  </li>
  <li><p>For each layer <span class="math-container">$l = 0, \dots, L - 1$</span></p>
  <ul>
  <li>Comment 5: <span class="math-container">$l = 0$</span> is the input layer and <span class="math-container">$L$</span> is the output layer</li>
  </ul>
  <ol start="2">
  <li>For <span class="math-container">$k=1, \dots, c(l)$</span>
  <ul>
  <li>Comment 6: for example, <span class="math-container">$n_l^k = n_2^3$</span> is the third neuron at the first hidden layer</li>
  </ul>
  <ol>
  <li>Let <span class="math-container">$M = \sum_{h=0}^{l-1} c(h)$</span>
  <ul>
  <li>Comment 7: <span class="math-container">$M$</span> is the number of neurons processed so far in the previous layers (excluding the neurons in the current layer)</li>
  </ul>
  </li>
  <li><span class="math-container">$i = k + M$</span></li>
  <li>For <span class="math-container">$t = 1, \dots, c(l+1)$</span>
  <ol>
  <li><span class="math-container">$j = t + c(l) + M$</span>
  <ul>
  <li><span class="math-container">$j$</span> is basically the index of the graph <span class="math-container">$G$</span> that corresponds to the neuron <span class="math-container">$t$</span> in the next layer <span class="math-container">$l+1$</span></li>
  </ul>
  </li>
  <li>Set <span class="math-container">$G_{ij} = 1$</span></li>
  </ol>
  </li>
  </ol>
  </li>
  </ol>
  </li>
  <li><p>Return the matrix <span class="math-container">$G$</span></p>
  </li>
  </ol>
  <p>The time complexity of this algorithm should roughly be <span class="math-container">$\mathcal{O}(L* {\max_l c(l)}^2)$</span>. 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?</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-12-15T16:42:25.707Z
Answers.Text: 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$).
Answers.UserDisplayName: GraftCraft
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-12-15T16:48:14.760Z
Answers.Text: 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.
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-12-15T16:55:04.707Z
Answers.Text: 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!
Answers.UserDisplayName: GraftCraft
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-12-15T14:36:01.150Z
Answers.LastActivityDate: 2021-12-15T15:27:32.110Z
Answers.LastEditDate: 2021-12-15T15:27:32.110Z
Answers.UserDisplayName: nbro
Body: <p>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.</p>
  <p><strong>Question:</strong> Is it possible to construct such an algorithm, and if so, how would you formalize it?</p>
  <hr />
  <p><strong>Example [Shallow Feedforward Neural Network (SNN)]</strong></p>
  <p>To illustrate the problem, consider an SNN, defined as a mapping <span class="math-container">$f=\left(f_1(\mathbf{x}), \ldots, f_m(\mathbf{x})\right): \mathbb{R}^n\rightarrow\mathbb{R}^m$</span> where for <span class="math-container">$k=1,\ldots,m$</span></p>
  <p><span class="math-container">\begin{align}
          f_k(\mathbf{x}) &amp;= \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}</span>
  and <span class="math-container">$w_{i,j}^{(k)}\in\mathbb{R}$</span> is fixed for all <span class="math-container">$i,j,k \in \mathbb{N}$</span> and <span class="math-container">$\rho:\mathbb{R}\rightarrow\mathbb{R}$</span> is a continuous mapping.</p>
  <p>I want to determine the nodes that make up the FNN, where a node <span class="math-container">$N^{\rho}: \mathbb{R}^n\rightarrow\mathbb{R}$</span> is defined as a mapping
  <span class="math-container">\begin{align} \label{eq:node}
          &amp;&amp; \quad &amp;&amp; N^{\rho}(\mathbf{x}) &amp;= \rho\left(\sum_{i=1}^n w_i x_i + w_0 \right), &amp; \mathbf{x}=(x_1,\ldots,x_n)\in\mathbb{R}^n
  \end{align}</span>
  where <span class="math-container">$\mathbf{w}=(w_0, \ldots,w_n)\in\mathbb{R}^{n+1}$</span> is fixed.</p>
  <p>Clearly (to me) I can write each <span class="math-container">$f_k$</span> as</p>
  <p><span class="math-container">\begin{align}
      f_k(\mathbf{x}) &amp;= \sum_{j=1}^{\ell} w_{j,k}^{(2)} N^{\rho}_j(\mathbf{x}) + w_{0,k}^{(2)},
  \end{align}</span>
  where <span class="math-container">$N^{\rho}_{j}$</span> is a node for <span class="math-container">$j=1,\ldots,\ell$</span>. Now I see that <span class="math-container">$f_k$</span> 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?</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-12-15T13:19:16.583Z
Comments.Text: 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?
Comments.UserDisplayName: nbro
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-12-15T13:34:05.027Z
Comments.Text: 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.
Comments.UserDisplayName: GraftCraft
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-12-15T13:38:01.923Z
Comments.Text: 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?
Comments.UserDisplayName: nbro
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-12-15T13:39:49.427Z
Comments.Text: Exactly, the edges should just represent connectivity, so an adjacency matrix is sufficient.
Comments.UserDisplayName: GraftCraft
Tags: <neural-networks><feedforward-neural-networks><graphs>
Title: How to uniquely associate a directed graph with a feedforward neural network?
UserDisplayName: GraftCraft
ThreadText: # How to uniquely associate a directed graph with a feedforward neural network?
  
  (Asked by: username_0 on 2021-12-15)
  
  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?
  
  **Tags:** neural-networks, feedforward-neural-networks, graphs
  > **Comments:**
  > **username_1**: 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?  
  > **username_0**: 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.  
  > **username_1**: 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?  
  > **username_0**: Exactly, the edges should just represent connectivity, so an adjacency matrix is sufficient.  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2021-12-15. Score: 0 | Accepted answer
  
  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?
  
  > **Comments:**
  > **username_0**: 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$).  
  > **username_1**: 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.  
  > **username_0**: 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!  
  
  ---
  
  