Why Represent Dependencies as a Graph?
When several derived variables depend on one another, recalculating them in an arbitrary sequence can leave some values based on outdated inputs. If a score is calculated from a total, and a category is then calculated from that score, the total must be updated before the score, and the score before the category. A directed dependency graph makes these requirements explicit. The earlier material on passive imputation establishes why derived variables must remain consistent with their defining formulas; here, the focus is on organizing their recalculation.
A graph is especially useful when one derived variable feeds several others, or when a later variable combines results from multiple branches. It records which variables must be available before each formula can be evaluated. It does not determine the statistical model for an incomplete variable, and it is not a causal diagram.
For example, if \(T=A+B\) and \(M=T/2\), the direct edges are \(A \to T\), \(B \to T\), and \(T \to M\). There is no direct edge \(A \to M\), because the formula for \(M\) uses \(T\), not \(A\). Nevertheless, \(A\) is an indirect dependency of \(M\) along the path \(A \to T \to M\). This distinction keeps the graph faithful to the formulas while still showing how updates can propagate.
Source variables are variables whose values are supplied to the derivation rather than computed by the derived-variable formulas being scheduled. They belong in the graph because they are inputs, but they are not recalculated by this schedule. The order among source variables is immaterial unless one of them is itself derived elsewhere in the graph.
Finding an Order in a DAG
A topological ordering of a directed graph places each node before every node to which it has an outgoing edge. For recalculation, this means each input is available before the formula that uses it. A graph can have more than one topological ordering: the required constraints matter, not the particular order chosen among unrelated variables.
A practical way to construct such an order is repeatedly to select a node with no incoming edges among the nodes still being considered, append it to the order, and remove its outgoing edges. A node with no incoming edges is one whose remaining prerequisites have already been handled. If nodes remain but none has zero incoming edges, the remaining graph contains a cycle.
Include each source variable and each derived variable. Write down the inputs used directly by every derived-variable formula.
For each formula defining \(v\), draw \(u \to v\) for every variable \(u\) used in that formula.
Repeatedly select a node with no remaining incoming edges. If all nodes are selected, the selection order is valid. If nodes remain and none can be selected, investigate a cycle.
After an upstream value changes, update affected derived variables in an order that respects their edges. Do not use an old intermediate value when its inputs have already changed.
The reason the selection procedure works is direct: when a node is selected, all its incoming neighbors have already been selected, so its inputs precede it in the resulting order. If the procedure selects every node, every edge therefore points forward in the order. Conversely, suppose the procedure stops with nodes remaining. Each remaining node has at least one incoming edge from another remaining node. Following incoming edges must eventually revisit a node, because there are finitely many nodes. The repeated portion forms a directed cycle. Thus, stopping early is a cycle diagnostic, not merely a failure to find a preferred order.
Worked Example: A Score, a Category, and a Risk Index
Consider hypothetical records containing weight \(W\) in kilograms, height \(H\) in metres, and age \(A\) in years. Define \(B=W/H^2\), a category \(C\) that is “standard” when \(18.5 \leq B < 25\) and “outside” otherwise, and a risk index \(R=B+0.1A\), measured in index points. Determine the graph and a valid recalculation order. For one record, let \(W=72\), \(H=1.80\), and \(A=40\).
The BMI-like derived quantity \(B\) uses \(W\) and \(H\), so the graph has edges \(W \to B\) and \(H \to B\). The category uses \(B\), giving \(B \to C\). The risk index uses both \(B\) and \(A\), giving \(B \to R\) and \(A \to R\). The source nodes \(W,H,A\) can be placed first; then \(B\) must precede both \(C\) and \(R\). Either \(C\) or \(R\) can come first after \(B\), because neither formula uses the other.
Substituting the hypothetical values,
Since \(18.5 \leq 22.22 < 25\), the category is “standard.” The risk index is
One valid order is \(W,H,A,B,C,R\); another is \(W,H,A,B,R,C\). The graph permits either because \(C\) and \(R\) are separate descendants of \(B\). If weight changes, recalculate \(B\) first, then recalculate both \(C\) and \(R\).
Branching Dependencies and Multiple Valid Orders
A derived variable can have several inputs, and one intermediate variable can feed multiple branches. In such graphs, a valid order is a constraint-respecting sequence, not a unique recipe. The key test is simple: for every arrow, its tail must appear before its head.
Worked Example: Recalculating Two Branches Before Combining Them
Suppose hypothetical measurements \(U=6\) and \(V=9\) define a sum \(S=U+V\). Define a centered quantity \(C=S-10\), a flag \(F=1\) if \(C \geq 5\) and \(F=0\) otherwise, and a second branch \(D_2=2D\), where \(D=3\). Finally, let \(Q=C+D_2\). Find the graph, two valid orders, and the values for this record.
The direct dependencies are \(U \to S\), \(V \to S\), \(S \to C\), \(C \to F\), \(D \to D_2\), and \(C \to Q\), \(D_2 \to Q\). In particular, \(Q\) must wait for both \(C\) and \(D_2\). The branch producing \(F\) does not have to be completed before \(D_2\), because \(F\) is not an input to \(Q\).
Two valid orders, including the source nodes for clarity, are \(U,V,D,S,C,D_2,F,Q\) and \(D,U,V,D_2,S,C,Q,F\). In both, every input precedes its dependent variable. For the first order, for example, \(S\) follows \(U,V\); \(C\) follows \(S\); and \(Q\) follows both \(C\) and \(D_2\).
The arithmetic is
so \(F=1\), since \(C \geq 5\). On the other branch,
If \(U\), \(V\), or \(D\) changes, update the descendants of that input in graph order. A change to \(D\) requires recalculating \(D_2\) and then \(Q\), but does not require recalculating \(S\), \(C\), or \(F\). The graph identifies both the ordering constraints and which branch is affected.
Cycles: When No One-Pass Order Exists
A cycle occurs when a chain of dependencies leads back to its starting variable. For example, if \(A=2B+1\) and \(B=A-3\), the graph contains both \(B \to A\) and \(A \to B\). There is no way to place \(A\) before \(B\) and \(B\) before \(A\) in one linear order. Recalculating one and then the other would use a value that is not yet updated in the same pass.
These equations happen to have a simultaneous algebraic solution: substituting \(B=A-3\) into \(A=2B+1\) gives \(A=2(A-3)+1\), hence \(A=5\) and \(B=2\). That fact does not create a valid one-pass recalculation order. A system of simultaneous equations is a different specification from a sequence of deterministic formulas that can be recalculated in dependency order.
Worked Example: Checking a Proposed Order and Finding a Cycle
Suppose \(P=Z+1\), \(Q=2P\), and \(R=Q+Z\). The graph has edges \(Z \to P\), \(P \to Q\), \(Q \to R\), and \(Z \to R\). The proposed order \(Z,P,R,Q\) is invalid because the edge \(Q \to R\) points backward: \(R\) is placed before an input it needs. An order such as \(Z,P,Q,R\) is valid.
Now add the formula \(P=R-4\) while retaining the other formulas. The graph then also has \(R \to P\), creating the cycle \(P \to Q \to R \to P\). No topological order exists. A cycle check reveals that the definitions do not specify a one-pass recalculation schedule. Before using these variables in a passive recalculation scheme, the formulas or variable definitions must be reviewed to remove the circular dependency or be reformulated as a different, explicitly specified system.
Practical Checks, Alternatives, and Limitations
A hand-written sequence is adequate for a short chain, but it is easy to overlook a dependency when formulas branch or when a variable is reused. A graph provides an auditable record of direct inputs; topological sorting then supplies a valid order. Checking a proposed sequence against every edge is often faster than recomputing all values to discover that one formula used a stale intermediate result.
A few checks help detect an incorrect graph or implementation:
- Check every formula’s inputs. Each input used directly by a derived formula should have an edge to that derived variable. Missing an edge can make an apparently valid order incorrect.
- Check every proposed order against every edge. For \(u \to v\), \(u\) must occur before \(v\). A list of variables alone does not establish validity.
- Check recalculation after an upstream update. Trace the affected descendants and ensure each is updated after its inputs. Otherwise, stored values can be algebraically inconsistent with the current inputs.
- Check for cycles when sorting stalls. If variables remain and each has a remaining prerequisite, inspect the definitions for a circular dependency rather than repeatedly trying different orders.
This representation has limits. The graph depends on correctly recording the formulas, including dependencies hidden inside software code. A formula that conditionally uses different inputs can be represented conservatively by including every input it may use. A formula involving a group-level summary or other across-record calculation may require the graph to represent that broader dependency as well. The graph also says nothing by itself about whether the imputation models are statistically appropriate; it organizes deterministic recalculation, not statistical compatibility or causal relationships.
Check Your Understanding
For each question, use the edge direction from input to derived variable. Solutions follow the questions.
- If \(M=X+Y\), \(N=M^2\), and \(G=1\) when \(N>10\) and \(G=0\) otherwise, list the edges and one valid order.
- Suppose \(A\) and \(B\) are sources, \(C=A+B\), \(D=2A\), and \(E=C+D\). Is \(A,B,C,D,E\) valid? Give another valid order if possible.
- A graph has edges \(J \to K\), \(K \to L\), and \(L \to J\). Can a one-pass recalculation order exist? Explain using the ordering constraints.
- In the definitions \(S=U+V\), \(T=S-2\), and \(F=1\) if \(T \geq 0\), \(F=0\) otherwise, \(U\) changes. Which derived variables need updating, and in what order?
Solutions. (1) The edges are \(X \to M\), \(Y \to M\), \(M \to N\), and \(N \to G\). One valid order is \(X,Y,M,N,G\), since every input precedes the derived variable that uses it.
(2) The edges are \(A \to C\), \(B \to C\), \(A \to D\), \(C \to E\), and \(D \to E\). The proposed order \(A,B,C,D,E\) is valid: \(C\) and \(D\) both precede \(E\). Another valid order is \(B,A,D,C,E\). The order among \(C\) and \(D\) can vary, but both must precede \(E\).
(3) No. The edges require \(J\) before \(K\), \(K\) before \(L\), and \(L\) before \(J\). Together these require \(J\) before itself in the ordering, which is impossible. The graph contains a directed cycle.
(4) Recalculate \(S\) first, then \(T\), then \(F\). The dependency path is \(U \to S \to T \to F\). Updating \(T\) before \(S\), or \(F\) before \(T\), would use an outdated input.