5
$\begingroup$

Is there a common name for the type of directed acyclic graph structure used in fully-connected neural networks?
E.g.

enter image description here

To be specific, I'm speaking of a directed graph, $G=(V,E)$, whose vertices can be partitioned into $k$ non-empty disjoint sets $V_1, ..., V_k$ such that $V = \displaystyle\bigcup_{i=1}^k V_i$ and $E = \displaystyle\bigcup_{i=1}^{k-1} V_i\times V_{i+1}$.

$\endgroup$
1
  • $\begingroup$ I haven't been able to find a common name for this. I would call it a complete layered directed graph or something. A neural network with two layers is called a complete bipartite graph. $\endgroup$ Apr 21 '17 at 12:49
2
$\begingroup$

No. At least not up to my knowledge.

If you only have an input layer and an output layer, the graph $G = (V, E)$ is bipartite. The "bi" means you can make two sets of nodes $V_1 \cap V_2 = \emptyset$ with $V_1 \cup V_2 = V$ and all edges $(v_1, v_2) \in E: v_1 \in V_1 \land v_2 \in V_2$.

The more general term is $k$-partite (see Wikipedia). A neural network with $k$ layers (including input and output) is $k$-partite (one also says it is "multipartite").

edit: I've just realized that this is not the exact class you want. The set of all $k$-partite graphs contains all neural networks with $k$ layers, but not only simple multilayer perceptron architectures. It also contains architectures like DenseNets and more. But I guess "$k$-partite directed graph" is as close as you get without saying "multilayer perceptron graph structure" or something similar.

edit: Thanks to Chiel ten Brinke, I've realized that $k=2$ for any layered network (without residual connections). Just put all even-numbered layer nodes in one set and all odd-numbered layer nodes in another set.

$\endgroup$
4
  • 1
    $\begingroup$ This is not correct. The example of the OP is also bipartite, as it is 2-colorable. The generalization of k-partite has to do with more colors being needed for a valid colorization. Look at de.wikipedia.org/wiki/K-partiter_Graph $\endgroup$ Apr 21 '17 at 10:15
  • $\begingroup$ @ChieltenBrinke Thank you very much for this comment. While you are correct that it is also bipartite (and I didn't realize that before), I don't see where my post is (or was) wrong. Could you please clarify that? $\endgroup$ Apr 21 '17 at 10:32
  • $\begingroup$ Any $k$-partite graph is also $k+1$ partite, isn't it? $\endgroup$ Apr 21 '17 at 10:33
  • $\begingroup$ Strictly speaking that is correct, but the intention of the answer was to give a characterizing name for the class of graphs described by the OP. $\endgroup$ Apr 21 '17 at 11:07
2
$\begingroup$

In the book Planning Algorithms by Steven M. LaValle, there is another name for that graph on page 65.

A layered graph is a graph that has its vertices partitioned into a sequence of layers, and its edges are only permitted to connect vertices between successive layers.

Although this is more general than the "fully-connected" case.

In addition, I found the name to be quite useless to find other literature. It seems to only give results on a different concept, layered graph drawing.

$\endgroup$
1
  • $\begingroup$ Using your definition we see every digraph $G=(V,E)$ can be partitioned into the layers $\{\{v\}:v\in V\}$ also since $E=\bigcup_{(u,v)\in E(G)}\{u\}\times \{v\}$ its edges only connect vertices between successive layers. Thus all digraphs are "layered graphs" using "Steven M. LaValle" terminology i.e. that definition is essentially useless. $\endgroup$
    – Ethan
    Dec 30 '18 at 14:10
2
$\begingroup$

For any digraphs $A$ and $B$ a map $f$ is referred to as a full homomorphism from $A$ to $B$ iff there is a homomorphism from $A$ to $B$ satisfying $\small \forall u,v\in V(A)((a,b)\not\in E(A)\implies (f(u),f(v))\not\in E(B))$, this is fairly common notation (e.g. here are several papers using this terminology 1,2,3), so naturally when there exists a full homomorphism from one digraph to another digraph then the first digraph is said to be fully homomorphic to the second one. Now with that said the digraphs you are describing are exactly those that are fully epimorphic to directed paths.

To see why note if any digraph $G=(V,E)$ has a surjective full homomosphism to any directed path $P=(U,R)$ where we have $U=\{1,2,3,\ldots n\}$ and $R=\{(1,2),(2,3),(3,4),\ldots (n-1,n)\}$ then there must exist a surjection $f:\{1,2,3,\ldots n\}\to V$ satisfying $(i,j)\in R\iff (f(i),f(j))\in E$ thus we know $\small E=\{(f(i),f(j)):(i,j)\in R\}=\bigcup_{(i,j)\in R}f^{-1}[\{i\}]\times f^{-1}[\{j\}]=\bigcup_{k=1}^{n-1}f^{-1}[\{k\}]\times f^{-1}[\{k+1\}]$ where $f$ is a surjection and all the fibers $\small \{f^{-1}[\{1\}],f^{-1}[\{2\}],\ldots f^{-1}[\{n\}]\}=\text{coim}(f)$ must partition $V$.

$\endgroup$

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.