# What is a Dynamic Computational Graph?

Frameworks like PyTorch and TensorFlow through TensorFlow Fold support Dynamic Computational Graphs and are receiving attention from data scientists.

However, there seems to be a lack of resource to aid in understanding Dynamic Computational Graphs.

The advantage of Dynamic Computational Graphs appears to include the ability to adapt to a varying quantities in input data. It seems like there may be automatic selection of the number of layers, the number of neurons in each layer, the activation function, and other NN parameters, depending on each input set instance during the training. Is this an accurate characterization?

What are the advantages of dynamic models over static models? Is that why DCGs are receiving much attention? In summary, what are DCGs and what are the pros and cons their use?

The short answer from a theoretical perspective is that ...

A Dynamic Computational Graph is a mutable system represented as a directed graph of data flow between operations. It can be visualized as shapes containing text connected by arrows, whereby the vertices (shapes) represent operations on the data flowing along the edges (arrows).

Note that such a graph defines dependencies in the data flow but not necessarily the temporal order of the application of operations, which can become ambiguous in the retention of state in vertices or cycles in the graph without an additional mechanism to specify temporal precedence.

The short answer from an applications development perspective is that ...

A Dynamic Computational Graph framework is a system of libraries, interfaces, and components that provide a flexible, programmatic, run time interface that facilitates the construction and modification of systems by connecting a finite but perhaps extensible set of operations.

The PyTorch Framework

PyTorch is the integration of the Torch framework with the Python language and data structuring. Torch competes with Theano, TensorFlow, and other dynamic computational system construction frameworks.

———   Additional Approaches to Understanding   ———

Arbitrary Computational Structures of Arbitrary Discrete Tensors

One of the components that can be used to construct a computational system is an element designed to be interconnected to create neural networks. The availability of these supports the construction of deep learning and back-propagating neural networks. A wide variety of other systems involving the assembly of components that work with potentially multidimensional data in arbitrarily defined computational structures can also be constructed.

The data can be scalar values, such as floating-point numbers, integers, or strings, or orthogonal aggregations of these, such as vectors, matrices, cubes, or hyper-cubes. The operations on the generalization of these data forms are discrete tensors and the structures created from the assembly of tensor operations into working systems are data flows.

Points of Reference for Understanding the Dynamic Computation Concept

Dynamic Computational Graphs are not a particularly new concept, even though the term is relatively new. The interest in DCGs among computer scientists is not as new as the term Data Scientist. Nonetheless, the question correctly states that there are few well-written resources available (other than code examples) from which one can learn the overall concept surrounding their emergence and use.

One possible point of reference for beginning to understand DCGs is the Command design pattern which is one of the many design patterns popularized by the proponents of object-oriented design. The Command design pattern considers operations as computation units the details of which are hidden from the command objects that trigger them. The Command design pattern is often used in conjunction with the Interpreter design pattern.

In the case of DCGs, the Composite and Facade design patterns are also involved to facilitate the definition of plug-and-play discrete tensor operations that can be assembled together in patterns to form systems.

This particular combination of design patterns to form systems is actually a software abstraction that largely resembles the radical idea that led to the emergence of the Von Neumann architecture, central to most computers today. Von Neumann's contribution to the emergence of the computer is the idea of permitting arbitrary algorithms containing Boolean logic, arithmetic, and branching to be represented and stored as data -- a program.

Another forerunner of DCGs is expression engines. Expression engines can be as simple as arithmetic engines and as complex as applications such as Mathematica. A rules engine is a little like DCGs except that rules engines are declarative and meta-rules for rules engines operate on those declarations.

Programs Manipulating Programs

What these have in common with DCGs is that the flow of data and operations to be applied can be defined at run time. As with DCGs, some of these software libraries and applications have APIs or other mechanisms to permit operations to be applied to functional details. It is essentially the idea of a program permitting the manipulation of another program.

Another reference point for understanding this principle at a primitive level is the switch-case statement available in some computer languages. It is a source code structure whereby the programmer essentially expresses, "We're not sure what must be done, but the value of this variable will tell the real-time execution model what to do from a set of possibilities."

The switch-case statement is an abstraction that extends the idea of deferring the decision as to the direction of computation until run time. It is the software version of what is done inside the control unit of a contemporary CPU and an extension of the concept of deferring some algorithm details. A table of functors (function pointers) in C or polymorphism in C++, Java, or Python are other primitive examples.

Dynamic Computation takes the abstraction further. They defer most if not all of the specification of computations and the relationships between them to run time. This comprehensive generalization broadens the possibilities of functional modification at run time.

Directed Graph Representation of Computation

That's what the Dynamic Computational model is. Now for the Graph part.

Once one decides to defer the choice of operations to be performed until run time, a structure is required to hold the operations, their dependency relationships, and perhaps mapping parameters. Such a representation is more than a syntactic tree (such as a tree representing the hierarchy of source code). Unlike an assembly language program or machine code, it must be easily and arbitrarily mutable. It must contain more information than a data flow graph and much more than a memory map. What must that data structure that specifies the computational structure look like?

Fortunately, any arbitrary, finite, bounded algorithm can be represented as a directed graph of dependencies between specified operations. In such a graph, the vertices (often represented as nodes of various shapes when displayed) represent operations performed on the data and the edges (often represented as arrows when displayed) are digital representations of information originating resulting from some operation (or system input) and upon which other operations (or system output) depend.

Keep in mind that the directed graph is neither an algorithm (in that a precise sequence of operations is specified) nor a declaration (in that data can be explicitly stored and loops, branches, functions, and modules may be definable and nested).

Most of these Dynamic Computational Graph frameworks and libraries permit the components to do computations on the component input that support machine learning. Vertices in the directed graph can be simulations of neurons for the construction of a neural net or components that support differential calculus. These frameworks present possibilities of constructs that can be used for deep learning in a more generalized sense.

In the Context of Computer History

Again, nothing mentioned thus far is new to computer science. LISP permits computational schematics to be modified by other algorithms. And generalized input dimensionality and numerocity is built into a number of longstanding plug-and-play interfaces and protocols. The idea of a framework for learning dates back to the same mid-Twentieth Century period too.

What is new and gaining in popularity is a particular combination of integrated features and the associated set of terminology, an aggregation of existing terminology for each of the features, leading to a wider base for comprehension by those already studying for and working in the software industry.

• Contemporary (trendy) flavor of API interfaces
• Object orientation
• Discrete tensor support
• The directed graph abstraction
• Interoperability with popular languages and packages that support big data, data mining, machine learning, and statistical analysis
• Support for arbitrary and systematic neural network construction
• The possibility of dynamic neural network structural adaptation (which facilitates experimentation on neural plasticity)

Many of these frameworks support adaptability to changing input dimensionality (number of dimensions and the range of each).

Similarity to Abstract Symbol Trees in Compilers

A dependency graph of inputs and outputs of operations also appears within abstract symbol trees (AST), which some of the more progressive compilers construct during the interpretation of the source code structure. The AST is then used to generate assembler instructions or machine instructions in the process of linking with libraries and forming an executable. The AST is a directed graph that represents the structure of data, operations performed, and the control flow specified by the source code.

The data flow is simply the set of dependencies between operations, which must be inherent in the AST for the AST to be used to create execution instructions in assembler or machine code that precisely follows the algorithm specified in the source code.

Dynamic Computational Graph frameworks, unlike switch-case statements or AST models in compilers, can be manipulated in real-time, optimized, tuned (as in the case of plastic artificial nets), inverted, transformed by tensors, decimated, modified to add or remove entropy, mutated according to a set of rules, or otherwise translated into derivative forms. They can be stored as files or streams and then retrieved from them.

This is a trivial concept for LISP programmers or those that understand the nature of John von Neumann's recommendation to store operational specifications as data. In this later sense, a program is a data stream to instruct, through a compiler and operating system, a dynamic computational system implemented in VLSI digital circuitry.

In the question is the comment that one doesn't, "Need to have data set -- that all the instances within it have the same, a fixed number of inputs." That statement does not promote accurate comprehension. There are clearer ways to say what is true about input adaptability.

The interface between a DCG and other components of an overall system must be defined, but these interfaces may have dynamic dimensionality or numerocity built into them. It is a matter of abstraction.

For instance, a discrete tensor object type presents a specific software interface, yet a tensor is a dynamic mathematical concept around which a common interface can be used. A discrete tensor may be a scalar, a vector, a matrix, a cube, or a hypercube, and the range of dependent variables for each dimension may be variable.

It can be the case that the number of nodes in a layer of the system defined in a Dynamic Computational Graph can be a function of the number of inputs of a particular type, and that too can be a computation deferred to run time.

The framework may be programmed to select layer structure (an extension of the switch-case paradigm again) or calculate parameters defining the structure sizes and depth or activation. However, these sophisticated features are not what qualifies the framework as a Dynamic Computational Graph framework.

What Qualifies a Framework to Support Dynamic Computational Graphs?

To qualify as a Dynamic Computational Graph framework, the framework must merely support the deferring of the determination of algorithm to run time, therefore opening the door to a plethora of operations on the computational dependencies and data flow at run time. The basics of the operations deferred must include the specification, manipulation, execution, and storage of the directed graphs that represent systems of operations.

If the specification of the algorithm is NOT deferred until run time but is compiled into the executable designed for a specific operating system with only the traditional flexibility provided by low-level languages such as if-then-else, switch-case, polymorphism, arrays of functors, and variable-length strings, it is considered a static algorithm.

If the operations, the dependencies between them, the data flow, the dimensionality of the data within the flow, and the adaptability of the system to the input numerocity and dimensionality are all variable at run time in a way to create a highly adaptive system, then the algorithm is dynamic in these ways.

Again, LISP programs that operate on LISP programs, rules engines with meta-rule capabilities, expression engines, discrete tensor object libraries, and even relatively simple Command design patterns are all dynamic in some sense, deferring some characteristics to run time. DCGs are flexible and comprehensive in their capabilities to support arbitrary computational constructs in such a way to create a rich environment for deep learning experimentation and systems implementation.

When to Use Dynamic Computational Graphs

The pros and cons of DCGs are entirely problem-specific. If you investigate the various dynamic programming concepts above and others that may be closely tied to them in the associated literature, it will become obvious whether you need a Dynamic Computational Graph or not.

In general, if you need to represent an arbitrary and changing model of computation to facilitate the implementation of the deep learning system, mathematical manipulation system, adaptive system, or another flexible and complex software construct that maps to the DCG paradigm well, then a proof of concept using a Dynamic Computational Graph framework is a good first step in defining your software architecture for the problem's solution.

Not all learning software uses DCG's, but they are often a good choice when the systematic and possibly continuous manipulation of an arbitrary computational structure is a run time requirement.

• "PyTorch is the integration of the Torch framework for the Python language" – I think that this statement may be misinterpreted as "PyTorch is a wrapper library for the Torch framework for the Python language", which would be a false statement. You should probably rephrase it. – nbro Jul 9 '18 at 23:25
• "With Dynamic Computational Graph frameworks, unlike with switch-case statements or intermediate AST models in compilers, one can manipulate the operations" ... "translate them" – What do you mean by "translating operations"? – nbro Jul 10 '18 at 1:29

In short, dynamic computation graphs can solve some problems that static ones cannot, or are inefficient due to not allowing training in batches.

To be more specific, modern neural network training is usually done in batches, i.e. processing more than one data instance at a time. Some researchers choose batch size like 32, 128 while others use batch size larger than 10,000. Single-instance training is usually very slow because it cannot benefit from hardware parallelism.

For example, in Natural Language Processing, researchers want to train neural networks with sentences of different lengths. Using static computation graphs, they would usually have to first do padding, i.e. adding meaningless symbols to the beginning or end of shorter sentences to make all sentences of the same length. This operation complicates the training a lot (e.g. need masking, re-define evaluation metrics, waste a significant amount of computation time on those padded symbols). With a dynamic computation graph, padding is no longer needed (or only needed within each batch).

A more complicated example would be to (use neural network to) process the sentences based on its parsing trees. Since each sentence has its own parsing tree, they each requires a different computation graph, which means training with a static computation graph can only allow single-instance training. An example similar to this is the Recursive Neural Networks.

Many deep neural networks have a static data-flow graph, which roughly means that the structure of its computation (its computation graph) remains stable over different inputs. This is good since we can leverage this feature for performance, such as by mini-batching (processing a bunch of inputs at once).

But some neural networks could have a different computation graph for each input. This causes some problems (batching difficulties, graph construction is computationally expensive), and hence these networks are a bit hard to use.

The paper you link overcomes this problem by proposing a method that can batch several computation graphs into one. Then, we can do our usual NN techniques.

Benefits are speedups, which incentivizes researchers to explore different structures and be more creative I guess.

The advantage of Dynamic Computational Graphs appears to include the ability to adapt to a varying quantities in input data. It seems like there may be automatic selection of the number of layers, the number of neurons in each layer, the activation function, and other NN parameters, depending on each input set instance during the training. Is this an accurate characterization?

This is incorrect.

Dynamic Computational Graphs are simply modified CGs with a higher level of abstraction. The word 'Dynamic' explains it all: how data flows through the graph depends on the input structure,i.e the DCG structure is mutable and not static. One of its important applications is in NLP neural networks.