definition algorithm

The data structure Mycelium.jl is built on, and the two acyclicity questions that get confused with each other.

Sources: original to this vault (design and analysis; no single paper).

Theory (CT-ML wiki): Bayesian Inversion · Statistical Game · Open Model · Variational Free Energy

Bipartite: wires and nodes

A factor graph has two kinds of node:

  • variables — wires. They carry a belief and have no behaviour of their own.
  • factors — statistical games. They have channels, energies, entropies, inversions and (sometimes) parameters.

An edge attaches one named channel of a factor to one variable. Channels are named, not positional, because a factor has no distinguished input: which channel is input is decided per message, by Polarity Resolution.

dataxxmodelylosstdatatxinoutpredtargett!Emitting/Absorbing$Bidirectionaldataxxmodelylosstdatatxinoutpredtargett!Emitting/Absorbing$Bidirectional

Four factors, three variables, six edges. Note what is not a variable: the data. See Everything is a Factor.

Edges are directed; bidirectional is a case, not the default

Each edge carries one of three directions:

directionmessagesthe attached channel is
Emitting()factor → variable onlynever Observed()
Absorbing()variable → factor onlynever Unobserved()
Bidirectional()botheither, per message

A bidirectional edge is exactly what “implicit” means. A factor that can be run in either direction along a wire is a relation; one that cannot is a function.

This is also where non-learnable and one-way factors enter naturally: a data source is emitting-only, a loss is absorbing-only, and neither has parameters. They are not special cases bolted onto the framework — they are ordinary factors whose edge directions happen to be constrained.

The two acyclicity questions

These get confused constantly, and they are independent.

predicateon whatdecides
istree(g)the undirected bipartite graphwhether message passing is exact
isdag(g)the directed multigraphwhether the graph is Lux-compatible
  • istree is connectivity plus loop-freeness. On a tree, two sweeps give the true marginals and the true free energy (Schedules). Off a tree you are running loopy BP and nothing is guaranteed (Loopy Message Passing).
  • isdag reads the directions: an emitting edge contributes the arc factor → variable, an absorbing edge variable → factor, and a bidirectional edge contributes both, which is already a 2-cycle.

So any graph containing a bidirectional edge fails isdag by construction, and that is the correct behaviour rather than an artefact: isdag(g) is precisely the predicate “this graph could have been written in Lux”.

The supervised example above is a tree that is not a DAG — exact inference, not Lux-expressible. That combination is the point of the library.

The Euler characteristic

1 for a connected tree, 1 - L for a graph with L independent loops. It reappears in Bethe Free Energy as the sum of the counting numbers, which makes it a single integer measuring how badly the free-energy bookkeeping over-counts. The test suite asserts the two computations agree, since that is the cheapest possible check that the graph and the accounting have not drifted apart.

Copying is a variable of degree > 2

The copier of Open Models and Latent Channels does not need a node type. A variable connected to three factors is a copier: all three see the same value. Fan-out is therefore free, and the degree is exactly the number of consumers — which is also, not coincidentally, what the Bethe counting number corrects for.

Related: Everything is a Factor, Messages are Inversions, Schedules, graph