[adamnemecek]

I've been running into the idea of computational graphs a lot recently. It's at the core of Tensorflow (and NN in general) but it also comes up for example in Apple's AVFoundation where all audio processing happens in a graph of audio units. Does anyone know what's the theoretical foundation of computational graphs?

EDIT: I've created a wiki page for computational graphs. https://en.wikipedia.org/wiki/Computational_Graph. Add your input.

[mtrn]

There is the biological analogue, which has inspired neural networks:

> Recall that in our general definition a feed-forward neural network is a computational graph whose nodes are computing units and whose directed edges transmit numerical information from node to node.

> Each computing unit is capable of evaluating a single primitive function of its input. In fact the network represents a chain of function compositions which transfor m an input to an output vector (called a pattern).

From: https://page.mi.fu-berlin.de/rojas/neural/chapter/K7.pdf (1996)

Another ancestor would be the Data-Flow paradigm:

> .. programming paradigm that internally represents applications as a directed graph, similarly to a dataflow diagram. Applications are represented as a set of nodes (also called blocks) with input and/or output ports in them. These nodes can either be sources, sinks or processing blocks to the information flowing in the system. Nodes are connected by directed edges that define the flow of information between them.

From: https://paginas.fe.up.pt/~prodei/dsie12/papers/paper_17.pdf (2012)

[adamnemecek]

> There is the biological analogue, which has inspired neural network

I'm somewhat aware but it seems like the idea of a computational graph is the most generic computational idea I can think of and I'm surprised it's not more explored.

> Another ancestor would be the Data-Flow paradigm:

Oh yeah, data flow is definitely another one.

[Jasper_]

Functional programming can be represented as a graph, where calls are directed edges. Flow control is often analyzed in graph form in real compilers:

https://en.wikipedia.org/wiki/Control_flow_graph

[adamnemecek]

It's not just functional programming (but I do agree that it's better in functional programming). All the reverse engineering tools have some feature to represent assembly as a CFG which is super helpful.

[throwawayish]

> I'm somewhat aware but it seems like the idea of a computational graph is the most generic computational idea I can think of and I'm surprised it's not more explored.

ASTs?!

[adamnemecek]

Yeah, I think that ASTs are only a special case of computational graphs.

[YeGoblynQueenne]

>> Does anyone know what's the theoretical foundation of computational graphs?

Automata can be represented as graphs- that's the main idea. When you look at the typical automaton diagram with states and transitions- that's a graph (with states as vertices and transitions as edges).

I think the confusion arises from the fact that, while automata can be represented as graphs, graphs can represent a much broader array of processes and objects (e.g. belief networks or semantic networks). I guess you can represent pretty much anything as a graph.

So "computational graph" as I understand it, just stresses the point that what is represented is a unit of computation (a.k.a. an automaton a.k.a. a grammar a.k.a. a language etc. etc.) rather than some other kind of graph.

[adamnemecek]

> So "computational graph" as I understand it, just stresses the point that what is represented is a unit of computation (a.k.a. an automaton a.k.a. a grammar a.k.a. a language etc. etc.) rather than some other kind of graph.

Exactly. I think that the fact that the nodes represent a unit of computation is enough for it to be different from normal graphs I think.

[dluther]

Related: directed acrylic graphs.

https://en.wikipedia.org/wiki/Directed_acyclic_graph

[throwaway91111]

I think an SSA DAG might apply here as well.