A graph replaces an impossible table with local commitments

Pearl begins from a practical failure of exhaustive probability. Suppose a reasoning system contains many propositions, each uncertain and each potentially relevant to the others. A literal joint table must assign a number to every combination of values. With binary variables the number of rows doubles whenever one variable is added. Twenty variables demand more than a million rows; a hundred make enumeration absurd. Worse, the table conceals the reasons for its numbers. It records the completed joint distribution but not the modular judgements from which the distribution was assembled.

The 1986 paper proposes a representation that is at once numerical and structural. A node stands for a propositional variable, possibly multivalued. A directed link from one node to another records a direct probabilistic influence. Each root receives a prior distribution. Every other node receives a conditional distribution given its parents. The graph is acyclic, so the variables can be ordered with every parent before its child. Multiplying the local assessments in that order produces a complete joint probability distribution.

This factorisation does more than compress numbers. It declares which quantities a modeller treats as direct. When a variable’s parents have been fixed, its conditional distribution does not need every earlier variable. Missing parents are therefore substantive independence commitments. The graph serves as an audit trail: a reader can ask why an arc exists, why one is absent, and where a conditional table came from. Pearl contrasts this with an undifferentiated joint table, which may be mathematically complete while remaining cognitively and organisationally opaque.

The direction of an arrow has two roles that must be kept distinct. Algebraically, it determines how the joint distribution is factorised. Interpretively, Pearl argues that causal direction is often a useful organising convention because people can assess the effect of familiar causes more readily than they can assess arbitrary diagnostic inversions. But a probability distribution alone can admit multiple directed representations. Arrows do not become experimentally established causes merely because a conditional table has been written beside them.

Pearl calls such directed structures belief networks and also discusses Bayesian and influence-network terminology. The paper’s language predates some later standardisation. Contemporary readers often reserve “Bayesian network” for the probability factorisation and “causal Bayesian network” for a graph supplied with stronger causal semantics. Reading historically means preserving Pearl’s proposal while not importing every later theorem or convention into the 1986 text.

Paths become conditional-independence tests

A sparse graph becomes useful only if its topology can answer independence questions. Pearl therefore develops a graphical separation criterion. Along an undirected path, an intermediate node can appear in three orientations. A chain runs head to tail, X→M→Y or X←M←Y. A fork runs tail to tail, X←M→Y. A collider runs head to head, X→M←Y. Conditioning affects the collider differently from the chain and fork.

For a chain or fork, placing the middle node in the conditioning set blocks the path. Once the state of a common mediator or common cause is known, the path contributes no remaining association under the graph’s Markov assumptions. A collider behaves oppositely. The path is blocked by default, but observing the collider, or in Pearl’s definition one of its descendants, can open it. This asymmetry is the hinge of directional separation and later became widely known through the vocabulary of d-separation.

The logic prevents a common error. Two causes of the same effect need not be marginally associated. If the effect is observed, however, evidence for one cause can reduce the need for the other. In later teaching this is called explaining away. The phenomenon is already contained in the local fusion machinery: diagnostic support arriving through a shared child changes how its alternative parents should be believed.

Graphical separation matters twice. It validates local representation by showing which independences the directed structure entails. It also controls information flow. A message should not bounce back as if it were new evidence, and evidence sources that are separated by a node can be combined multiplicatively at that node. The graph is therefore not only a static map of relevance; it is the routing discipline for a distributed computation.

The network is designed as a society of small processors

Pearl’s computational aim is unusual in its explicit architecture. Each node is imagined as a processor responsible for one variable. It stores its local conditional information, maintains communication links to neighbouring processors, receives messages, updates its belief, and transmits only the consequences its neighbours need. There is no central table and no required global clock. When evidence is entered at one node, the disturbance propagates along active paths until the network reaches a new equilibrium.

This autonomy addresses more than processor speed. Pearl wants a system that can accept evidence at arbitrary locations, integrate several sources, produce beliefs at every node rather than only at a named query, and continue operating when new facts arrive. A sequential theorem prover often starts from a goal and searches for relevant premises. The propagation network instead maintains a distributed state of preparedness. Once quiescent, every node’s current belief is available locally.

The price of autonomy is a strict message contract. A neighbour must receive a summary that excludes the neighbour’s own earlier contribution. Otherwise the same evidence would be counted again after travelling out and back. Pearl’s update equations accomplish this through ratios or through products that deliberately omit the destination branch. This “do not return a message to its source unchanged” rule is one of the deepest reusable ideas in message-passing algorithms.

Pearl stresses qualitative advantages of this organisation: parallelism, modularity, robustness to the order in which evidence arrives, and an interpretation compatible with associative retrieval. Those are architectural arguments, not a claim that human brains literally implement the equations. The paper repeatedly uses cognitive motivation, but its mathematical achievement is a probability algorithm for a defined class of graphs.

Belief is the product of support from above and below

Consider first a rooted tree in which every node has at most one parent. Cut the link between a node B and its parent A. Evidence on B’s descendant side of the cut supplies diagnostic support for each possible state of B. Pearl denotes this likelihood-like vector by λ(B). Evidence on the other side supplies predictive or causal support, denoted π(B). Because the two evidence sets are conditionally independent given B, Bayes’s rule allows their contributions to be multiplied.

The predictive term π(B) is formed by averaging the conditional table P(B|A) against the support currently assigned to A after removing evidence from B’s own branch. The diagnostic term λ(B) is a product of the likelihood vectors sent by B’s independent child subtrees. In Pearl’s discrete formulation, vectors and matrices make these operations concrete. A message from a child is multiplied componentwise with other child messages; the conditional matrix then translates support between the state spaces of parent and child.

Multiplication is justified by graph separation, not by a generic idea that “more evidence means multiply”. Child branches may be fused only when the required conditional independence holds. If an unrepresented common influence couples the sensors, naive multiplication double-counts information and can make the posterior dramatically overconfident. A belief network is therefore a licence to combine evidence only to the extent that its topology and probability tables are defensible.

Virtual evidence extends the same mechanism. Instead of asserting that a variable has one observed state, a source can supply relative likelihoods over its states. A laboratory report, an uncertain witness or a noisy sensor may contribute a likelihood vector rather than a categorical fact. Pearl’s formulation makes this natural: hard evidence is only a likelihood vector with zero weight on incompatible states.

The distinction between causal and diagnostic support is representational, not metaphysical. Messages called π travel with arrow direction and messages called λ travel against it. Both are probability summaries. A downstream observation can change beliefs about upstream causes because Bayes’s rule reverses conditioning locally; the network need not reverse its stored arrows or rebuild its tables.

One local rule supports prediction, diagnosis and intercausal reasoning

The tree case is easiest because each link separates the graph into two independent evidence regions. At a node B with parent A and children D₁,…,Dₖ, λ(B) is the componentwise product of child messages. BEL(B) is that product multiplied by the predictive vector arriving from A. To send a diagnostic message to A, B sums over its own states after including every child message. To send a predictive message to one child Dⱼ, B uses its current belief-like product but excludes Dⱼ’s λ message.

The exclusion rule makes messages directional summaries of disjoint evidence. A message along B→Dⱼ represents all evidence on B’s side of that cut, translated into what Dⱼ needs. The returning message Dⱼ→B represents evidence on the other side. On a tree there is exactly one path between any pair of nodes, so the two summaries cannot unknowingly include each other. This is why the algorithm is exact without a global ledger of evidence provenance.

For a singly connected network with multiple parents, cutting one link does not necessarily isolate a simple ancestral and descendant subtree in arrow direction, but it still separates the underlying undirected graph. Pearl partitions the evidence around a node relative to each incident link and derives generalised π and λ messages. The node’s conditional table relates its own states jointly to the states of all parents. Updating a message can require summing over combinations of the other parents, but only local tables and incoming vectors are needed.

Later factor-graph notation makes this rule look especially uniform: variables multiply incoming factor messages, factors multiply their local function by incoming variable messages and sum out every variable except the destination. That later notation should not be projected backwards as Pearl’s exact presentation, but it clarifies the family resemblance. The laboratory below uses this sum-product form to implement the same tree computation and compares every marginal with direct enumeration.

A disturbance travels once along every active direction

At equilibrium, every node stores messages consistent with its neighbours and can report its current belief. Entering evidence changes one local likelihood vector. The affected processor updates its belief and sends new messages to neighbours. Each recipient repeats the process, but does not send the change straight back to the neighbour from which it arrived. On a singly connected graph the wave therefore advances along unique paths. After the disturbance has crossed the longest relevant path, no further values change.

Pearl illustrates propagation with tokens moving through a tree. One new item of evidence may produce outward waves; two pieces entered at different places may propagate simultaneously. Where their fronts meet, the local multiplication fuses them and the combined consequences continue. Because multiplication of independent support is commutative, the final equilibrium does not depend on which evidence item happened to arrive first, assuming exact arithmetic and a consistent network.

The local work per processor depends on its state space, degree and conditional table. For bounded node size and bounded degree, parallel propagation time is proportional to the network’s diameter, the longest path a change must cross. Total work is linear in the number of links for a tree. These claims are structural. They do not mean that every Bayesian network admits linear inference, since a multiply connected graph cannot be handled by this exact single-pass scheme without transformation or additional computation.

Four boundary conditions require explicit handling. A root has no parent message and uses its prior. A leaf has no child evidence unless observed, so its default diagnostic vector is all ones. Hard data at a node clamp or zero incompatible states. A “dummy” or virtual root can supply context when an ordinary root itself depends on background assumptions. These are not incidental coding details; they define what counts as absence of evidence and what enters as prior knowledge.

The exact contract ends where two undirected paths begin

A singly connected network may contain nodes with several parents and several children, but between any pair of nodes there is at most one undirected path. This topological condition, not the mere absence of directed cycles, protects the message decomposition. A directed acyclic graph can still contain an undirected loop. In such a multiply connected network, evidence can reach a node along two routes, and a locally returned summary may already contain some of the recipient’s own information.

Pearl’s paper is candid about the boundary. The exact autonomous propagation scheme is established for singly connected networks. For multiply connected networks the paper mentions methods including conditioning, clustering, and stochastic relaxation, and points to preprocessing or structural transformation. These approaches trade time, memory or repeated runs for restored independence. The later junction-tree method of Lauritzen and Spiegelhalter made one major route systematic by marrying parents, triangulating the graph and propagating between cliques.

The computational limit is not a historical footnote. Cooper later proved that exact probabilistic inference in general belief networks is NP-hard. No choice of message notation erases that worst case. Sparse tree structure creates tractability; dense interactions or unfortunate elimination order can create cliques whose tables are exponential in induced width. A production system must therefore disclose whether it is doing exact tree propagation, exact clustered inference, sampling, variational approximation, or an unverified loopy iteration.

Later work found that loopy belief propagation can be remarkably useful in coding, vision and statistical physics, but its interpretation changes. Yedidia, Freeman and Weiss connected fixed points, when they exist, to stationary points of a Bethe free-energy approximation. Kschischang, Frey and Loeliger’s factor-graph tutorial placed Pearl’s algorithm within a broader sum-product family. These are genuine descendants, not results contained in the primary paper.

Pearl also asks whether dependency data can reveal a causal tree

The paper’s third section changes tasks. The first two sections assume that a network and its conditional probabilities are available, then ask how to propagate evidence. The final section asks how a tree-structured representation might be constructed when what is given is a joint distribution, especially when empirical knowledge is dominated by pairwise relationships. This is a structure-recovery problem, and Pearl presents it as difficult.

Causal ordering supplies a modelling heuristic. People often find it easier to organise variables around generative direction, mechanisms and central coordinators than around an arbitrary alphabetical order. A tree has special computational advantages: sparse storage, unique paths and fast propagation. But a general distribution need not possess a faithful tree representation over the observed variables. Pearl therefore allows hidden or dummy variables and investigates restricted families for which adding such variables can make a star or tree decomposition possible.

The mathematical development focuses on distributions whose relevant structure is captured by second-order information. For dichotomous variables Pearl derives conditions under which a triple is star-decomposable, meaning that the three visible variables can be conditionally independent given a central hidden binary variable. The conditions involve signs and magnitudes of correlations. If pairwise dependencies have incompatible signs or violate derived inequalities, the desired star cannot exist within the stated family.

The reconstruction procedure examines overlapping triplets of leaves. Candidate triplets that share a common centre are joined, and new hidden nodes are introduced as needed. Four-leaf topologies can be distinguished through equality relations among pairwise quantities, after which local parameters can be recovered by solving the corresponding equations. Under the paper’s assumptions the process can build a tree in roughly linear structural work once the required pairwise information is available.

This programme differs sharply from Chow and Liu’s 1968 result in Paper 0015. Chow and Liu select, among trees on observed variables, the distribution minimising Kullback–Leibler divergence to a given discrete distribution; maximum-weight spanning tree solves the topology. Pearl is interested in causal interpretation and permits hidden centres to obtain exact decompositions for restricted families. One is a best observed-tree approximation with a global information objective. The other is a constrained exact-representation and recovery question, with different assumptions and failure modes.

Pearl closes with constraints and open questions. The available second-order information may be inaccurate. The required tree may not exist. Choosing where to introduce hidden variables is delicate. Distributions with higher-order interactions can agree on every pairwise relationship yet differ in essential structure, as the XOR family dramatically demonstrates. Approximate causal modelling remains a judgement-laden activity when exact decomposability fails.

The lasting contribution is a contract between structure and computation

Pearl’s paper is sometimes compressed into the slogan “belief propagation on trees”. That is correct but incomplete. The primary text links four claims. First, a graph can express conditional independence and factorise a joint distribution. Second, causal ordering can make local assessments intelligible, although probability alone does not settle causality. Third, singly connected topology makes exact distributed updating possible through complementary message types. Fourth, restricted dependency information may permit a tree representation to be recovered or tested.

The most durable idea is that structure buys computation only by making assumptions. A short message is sufficient because the graph says what becomes independent after a cut. Fast propagation is therefore not a numerical trick applied after modelling; it is the computational dividend of a structural claim. If the claim fails, efficiency can survive only by changing the representation, accepting approximation, or paying more.

This idea propagated widely. Junction-tree algorithms extend exact local computation to broader sparse graphs by clustering variables. Factor graphs expose the common sum-product skeleton behind Bayesian-network propagation, hidden Markov forward–backward recursions, coding algorithms and other dynamic programmes. Loopy belief propagation reuses local updates as an approximation on cyclic graphs. Modern probabilistic programming systems automate parts of this machinery, but they still confront the same question: which factorisation makes the requested posterior both meaningful and computable?

Exact polytree message-passing laboratory

The laboratory uses four binary variables in a singly connected network: root R influences A and B, and A influences C. Each selection changes local conditional probabilities or evidence. A generic sum-product implementation passes messages on the equivalent factor tree. Independently, exhaustive enumeration scores all sixteen assignments. The displayed marginal bars come from messages; the oracle line reports the largest difference from enumeration.

The deliberately contradictory option A=0 and C=1 does not break probability. It creates a low-likelihood observation under a reliable A→C channel, and the posterior distributes responsibility according to the tables. Hard evidence clamps A while C’s observation changes nothing upstream through that already fixed mediator. This is a useful separation check, not a model of sensor fallibility; virtual evidence would be appropriate for uncertain observations.

Memory studio

What remains after the messages become quiet

The paper turns conditional independence into an operational resource. The arrows do not merely decorate a probability table. They determine a factorisation, expose assumptions, separate evidence regions, and specify which summaries can cross each boundary. When the structure is a polytree, exact global posterior beliefs arise from local multiplication and marginalisation.

Its two-message vocabulary remains pedagogically powerful. Prediction and diagnosis are not rival modes of reasoning. Predictive support travels from causes towards consequences; diagnostic support travels from consequences towards possible causes; each node fuses both. The same stored conditional table participates in both directions because Bayes’s rule is implemented through messages rather than through a second reversed model.

The algorithm’s restraint is as important as its reach. Outgoing messages exclude the destination’s contribution. Colliders obey a different observation rule from chains. Hard evidence is distinguished from absence of evidence. Trees are distinguished from general DAGs. Structure recovery is distinguished from propagation on a known structure. Each distinction prevents a plausible but invalid shortcut.

For modern systems, audit the complete contract. What variables exist? Which arrows and omissions are justified? Are sensor errors conditionally independent? Are tables calibrated in the environment of use? Is the graph singly connected after directions are ignored? If not, what exact or approximate inference method is running, and what diagnostics support it? “Belief propagation” names a family; reliability depends on the particular graph, factors, messages and stopping rule.

The deepest lesson is architectural. Global coherence need not require a central processor, but decentralisation is not free. It requires interfaces whose summaries are sufficient and a topology that prevents information from returning disguised as independent evidence. Pearl’s belief network made that trade visible, mathematical and executable.