Computation graphs
Computation graphs
A computation graph records a calculation as small operations joined by arrows. Once a calculation is a graph, you can find every derivative by walking the graph backward. This walk is the core of automatic differentiation, or autograd.
The graph
Each node holds one value. Each operation, such as an add or a multiply, makes a new node from its parent nodes. Take
The forward values are \(c = 6\) and \(d = 8\). The graph records that \(d\) came from \(c\) and \(a\), and that \(c\) came from \(a\) and \(b\). The value \(a\) feeds two operations.
| Node | Operation | Parents | Value |
|---|---|---|---|
| \(a\) | input | none | \(2\) |
| \(b\) | input | none | \(3\) |
| \(c\) | multiply | \(a\), \(b\) | \(6\) |
| \(d\) | add | \(c\), \(a\) | \(8\) |
The graph has no loops. Each value depends only on values computed before it.
Local derivatives
Each operation knows its own derivatives with respect to its parents. Only two rules are needed for this graph:
| Operation | Derivative with respect to \(p\) | Derivative with respect to \(q\) |
|---|---|---|
| \(p + q\) | \(1\) | \(1\) |
| \(p \cdot q\) | \(q\) | \(p\) |
An add passes slope through unchanged. A multiply scales the slope by the other input.
The backward pass
Every node gets a gradient slot. It holds \(\frac{\partial d}{\partial \text{node}}\), the slope of the final output with respect to that node.
- Start at the output. Set its gradient to \(1\), since \(\frac{\partial d}{\partial d} = 1\).
- Visit the nodes in reverse order. At each node, multiply its gradient by each local derivative and add the result to that parent's gradient.
For the example:
- \(d = c + a\) sends \(1 \cdot 1 = 1\) to \(c\) and \(1\) to \(a\).
- \(c = a \cdot b\) sends \(1 \cdot b = 3\) to \(a\) and \(1 \cdot a = 2\) to \(b\).
The value \(a\) receives two contributions, so its gradient is \(1 + 3 = 4\). Check it directly: \(d = ab + a\), so \(\frac{\partial d}{\partial a} = b + 1 = 4\) and \(\frac{\partial d}{\partial b} = a = 2\).
A value used in several places adds up the gradient from each use. This is why the step says "add". Overwriting the slot would lose a path.
a, b = 2.0, 3.0
c = a * b
d = c + a
d_grad = 1.0
c_grad = d_grad * 1.0
a_grad = d_grad * 1.0
a_grad += c_grad * b
b_grad = c_grad * a
print("a:", a_grad, "b:", b_grad)
It prints a: 4.0 b: 2.0.
Visiting order
A node may only pass its gradient on after it has received every contribution. A topological order lists each node after all of its parents. Walking that list in reverse guarantees the rule.
A depth-first search builds the order. It visits every parent of a node first, then appends the node.
parents = {"a": [], "b": [], "c": ["a", "b"], "d": ["c", "a"]}
order, seen = [], set()
def visit(node):
if node not in seen:
seen.add(node)
for parent in parents[node]:
visit(parent)
order.append(node)
visit("d")
print(order)
print(list(reversed(order)))
The order is ['a', 'b', 'c', 'd']. The backward pass walks ['d', 'c', 'b', 'a']. By the time it reaches a, both c and d have already sent their gradients.
The build note at the end of this journey turns these steps into a Value class that records the graph and runs the backward pass automatically.
Sources
- Ian Goodfellow, Yoshua Bengio, and Aaron Courville, Deep Learning, Chapter 6: Deep Feedforward Networks, section 6.5 on computational graphs
- Andrej Karpathy, micrograd
Cards
What is a computation graph?
Reveal
A record of a calculation as nodes joined by operations. Each node holds one value, and each operation makes a new node from its parent nodes.
In a computation graph, what local derivatives does an add node \(p + q\) pass to its parents?
Reveal
\(1\) to each parent. An add passes the incoming gradient through unchanged.
In a computation graph, what local derivatives does a multiply node \(p \cdot q\) pass to its parents?
Reveal
\(q\) to \(p\), and \(p\) to \(q\). Each parent gets the incoming gradient times the other parent's value.
What gradient does the backward pass give the output node before it starts?
Reveal
\(1\), because the output's derivative with respect to itself is \(1\).
A value feeds two operations in a computation graph. How is its gradient computed?
Reveal
Add the gradient contributions from both uses. Overwriting the gradient slot would lose one path.
Let \(a = 2\), \(b = 3\), \(c = ab\), and \(d = c + a\). What are \(\frac{\partial d}{\partial a}\) and \(\frac{\partial d}{\partial b}\)?
Reveal
\(a\) gets \(1\) from the add and \(b = 3\) from the multiply, so \(\frac{\partial d}{\partial a} = 4\). \(b\) gets \(a = 2\), so \(\frac{\partial d}{\partial b} = 2\).
Why does the backward pass visit nodes in reverse topological order?
Reveal
A topological order lists each node after all its parents. In reverse, every node has received all of its gradient contributions before it passes its gradient on.