Computational Graph

A computational graph is a directed graph representing a computation through operations, values, and the dependencies between them. It expresses how a function is evaluated by combining simpler steps, rather than merely specifying its final formula. Computational graphs are important in machine learning, where they support model execution and automatic differentiation, and in numerical compilation, where they expose opportunities for optimizing execution and memory use. Their precise representation varies between systems: operations may form the nodes, with values carried along edges, or values may themselves be represented as nodes. (tensorflow.org)

Structure and evaluation

In an operation-centered representation, each node applies an operation to inputs supplied by incoming edges and produces outputs consumed by subsequent nodes. Values may be scalars, arrays, or tensors, including matrices. A node can represent a simple addition or a larger operation such as matrix multiplication. In TensorFlow, for example, graphs contain operation objects and tensor objects that describe the data flowing between operations. (tensorflow.org)

A finite computation without explicit looping is commonly represented as a directed acyclic graph. Evaluation follows dependencies: an operation executes after its required inputs become available. Branches can share intermediate results, so the representation is not necessarily a tree. This structure also provides the dependency information needed for backward differentiation. (docs.pytorch.org)

Consider the illustrative computation

Its graph contains multiplication, addition, and squaring operations. For $a=2$, $b=3$, and $c=1$, evaluation produces $u=6$, $v=7$, and $y=49$. The intermediate variables make the sequence of dependencies explicit.

Acyclicity is not a universal requirement for every graph-based programming system. Loops may be unrolled into repeated operations, represented by structured control-flow operations, or expressed using cyclic dataflow mechanisms. Thus, an executed differentiation graph and a graph representing an entire program need not have identical structures. TensorFlow’s original design explicitly supported cyclic dataflow graphs for control flow. (tensorflow.org)

Automatic differentiation

Computational graphs support differentiation by associating elementary operations with local derivative rules and combining them through the chain rule. Instead of deriving one expanded expression for the whole program, a differentiation system propagates derivative information through its constituent operations. For vector-valued computations, the corresponding local derivatives are described by Jacobian matrices, although implementations generally compute products with these matrices without constructing them explicitly. (docs.jax.dev)

Forward-mode differentiation propagates a directional change in the inputs alongside the original computation. For $f:\mathbb{R}^n\to\mathbb{R}^m$, it computes a Jacobian–vector product $J_f(x)p$. Reverse-mode differentiation starts with an output weighting and propagates sensitivities backward, computing a vector–Jacobian product. Reverse mode is particularly suitable for a scalar output depending on many inputs, whereas forward mode is often suitable when there are relatively few input directions of interest. (docs.jax.dev)

For the example above, reverse differentiation begins with $\partial y/\partial y=1$. Squaring gives $\partial y/\partial v=2v$; addition passes this sensitivity to both $u$ and $c$; multiplication then gives

At the specified inputs, these derivatives are $42$, $28$, and $14$. When an intermediate value contributes to an output through several paths, its derivative contributions are added. (docs.pytorch.org)

In artificial neural networks, backpropagation applies reverse-mode differentiation to compute the gradient of a loss function with respect to model parameters. An optimization method such as gradient descent then uses those gradients to update parameters. Graph evaluation, differentiation, and parameter updating are distinct stages, even when a framework combines them into one training routine. (docs.pytorch.org)

Static graphs, dynamic graphs, and tracing

A static graph is constructed before its execution and can be reused. A dynamic graph records dependencies while operations execute, allowing the recorded computation to reflect the branches actually taken. In PyTorch eager autograd, the differentiation graph is recreated during each forward execution, accommodating changes in Python control flow between iterations. (docs.pytorch.org)

Tracing offers another construction mechanism: a system executes or analyzes a function to capture operations in a reusable graph. TensorFlow’s tf.function captures TensorFlow operations, while AutoGraph converts supported Python control-flow constructs into graph-generating code. Python actions performed during tracing are not automatically graph operations; an ordinary print statement, for example, may run during tracing rather than on every subsequent graph execution. Different input signatures can also trigger retracing. (tensorflow.org)

These approaches can coexist. PyTorch compilation can capture graphs from eager programs and construct forward and backward graphs for compiled execution; consequently, “dynamic” and “compiled” are not mutually exclusive descriptions. (docs.pytorch.org)

Compilation and memory management

A graph exposes relationships across operations that a compiler can exploit. Transformations include constant propagation, elimination of repeated expressions, operation fusion, and buffer planning. Fusion combines operations into a larger execution unit, potentially reducing launch overhead and transfers of intermediate values to memory. On a graphics processing unit, fused operations may retain intermediates in registers or shared memory rather than writing them to device memory. (openxla.org)

Graph structure also informs scheduling for parallel computing and partitioning for distributed computing. Dependencies constrain execution order, while partitioning introduces communication between devices. Execution efficiency therefore depends on both computation and data movement. (openxla.org)

Reverse differentiation often requires intermediate values saved during forward execution. Activation checkpointing reduces their memory cost by retaining selected inputs and recomputing missing intermediates during the backward pass. This trades additional computation for lower memory usage; correctness requires recomputation to reproduce the relevant forward behavior. (docs.pytorch.org)

Differentiability and numerical limits

A computational graph does not make every operation differentiable. Discrete operations, undefined expressions, and nondifferentiable points require explicit handling or framework-specific derivative conventions. Moreover, differentiating an invalid operation before masking its output can still produce invalid gradients. In-place mutation can also interfere with differentiation when it overwrites values needed by the backward pass. (docs.pytorch.org)