D2.4 · LESSON 4 OF 6

Topological order

Apply the chain rule through a graph and implement the core of a scalar reverse-mode autodiff engine.

THE IDEA

Why the order is not optional

The forward pass must compute a node only after all of its inputs. The backward pass is the mirror image: a node may send its gradient to its inputs only after every node that uses it has already sent its share. Otherwise it passes along an incomplete number, and the error spreads to everything upstream.

A topological order is any ordering of the nodes where every node comes after its inputs. Run it forwards to compute values, and in reverse to send gradients.

Forward pass. Click nodes to compute them (blue = ready).

forward order: none

Backward pass. Click the operation nodes in the order you want to push gradients back. A node that goes too early pushes an incomplete gradient and turns red.

No backward order chosen yet.

Final ∂L/∂a from the correct backward pass:

Try the forward pass, then try different backward orders. A node that goes too early turns red and the final gradients come out wrong.

Predict first. Why is an arbitrary node order unsafe for the backward pass?

Chapter context

Backpropagation organizes repeated applications of the chain rule. The graph stores how values depend on earlier values. Reverse traversal accumulates how the final loss changes with each intermediate quantity.

TRY IT YOURSELF

Part 1. Do it hands-on

The graph has two nodes that are used twice, which is what makes the backward order matter.

Forward pass. Click nodes to compute them (blue = ready).

forward order: none

Backward pass. Click the operation nodes in the order you want to push gradients back. A node that goes too early pushes an incomplete gradient and turns red.

No backward order chosen yet.

Final ∂L/∂a from the correct backward pass:

To do: Run the forward pass: click the nodes in an order where every node comes after its inputs
To do: Run the backward pass: click the four operation nodes in an order that gives the same gradients as the correct engine
To do: Type the final value of ∂L/∂a that the correct backward pass produces

Part 2. Do it in code

Nodes are names. parents maps a name to the list of names it was computed from (leaves may be missing or empty). Write topo_order(out, parents): a list of every node that out depends on (and out itself, last) in which each node appears once, after all of its parents. A node shared by several users must appear only once.
Write is_topological(order, parents): True only if every node appears exactly once and after all of its parents (all parents must be in the order).
Write backward_order(out, parents): the order to visit nodes in the backward pass, i.e. the reverse of topo_order.

def topo_order(out, parents):
    # depth-first: visit the parents first, then add the node
    pass

def is_topological(order, parents):
    pass

def backward_order(out, parents):
    pass

parents = {"p": ["a", "b"], "q": ["p", "a"], "L": ["q"]}
print(topo_order("L", parents))   # a valid order such as ['a', 'b', 'p', 'q', 'L']

Ctrl/⌘ + Enter runs it

Stuck, or something not working? You can come back to it any time.

CHECK YOUR UNDERSTANDING

Why is arbitrary node order unsafe?

AA node may propagate before its full gradient is accumulated, so it sends an incomplete value upstream.BBackward needs the loss first, so any order that starts at the loss is safe.CArbitrary order is slower but always gives the same gradients.

Chapter reference: math, worked example & code

This section belongs to the whole chapter, so it is the same on every lesson in it and may cover a different lesson's topic. The code for the experiment you just ran is inside the experiment itself.

Math and notation

If $u=ab+c$ and $L=u^2$ , then

\frac{\partial L}{\partial a}=2ub,\quad \frac{\partial L}{\partial b}=2ua,\quad \frac{\partial L}{\partial c}=2u.

At a shared node x, add all downstream contributions: $\partial L/\partial x=\sum_j(\partial L/\partial u_j)(\partial u_j/\partial x)$ .

Worked example

Take a=2,b=3,c=1. Then u=7 and L=49. The upstream gradient into u is 14, giving dL/da=14×3=42, dL/db=14×2=28 and dL/dc=14. These are sensitivities, not new parameter values; an optimizer still needs a step size.

Reference code

The following example uses the Python standard library and does not call a remote service.

from math import isclose
a,b,c = 2.,3.,1.
u = a*b+c
assert u*u == 49
assert (2*u*b,2*u*a,2*u) == (42,28,14)
h = 1e-5
f = lambda x: (x*b+c)**2
assert isclose((f(a+h)-f(a-h))/(2*h), 42, rel_tol=1e-7)

Python examples are provided for study and local execution; this page does not execute Python.

Common mistakes

Forward values and gradients are different objects. Shared branches require addition of gradient contributions. Backpropagation computes derivatives; the optimizer changes parameters.