GitHub

Iterative Gaussian Belief Propagation

Iterative Gaussian belief propagation solves arbitrary Gaussian factor graphs by repeated message updates on a GaussianFactorGraph. Each iteration updates messages from factor nodes to variable nodes and from variable nodes back to factor nodes. Scheduling, damping, freezing, and warm-start graph updates are available for moment, canonical, and min-sum inference states.

The inference object determines which Gaussian belief propagation variant is run:

  • moment runs sum-product belief propagation in moment form and stores Gaussian marginals.
  • canonical runs sum-product belief propagation in canonical form and stores Gaussian marginals.
  • minsum runs min-sum belief propagation for MAP inference and stores MAP estimates.

Use moment or canonical when posterior means and covariances are needed. Use minsum when only the MAP estimate is needed.

Start from a Gaussian factor graph:

variables = [
    GaussianVariable(:x1, 1),
    GaussianVariable(:x2, 2),
    GaussianVariable(:x3, 1),
]

factors = [
    GaussianFactor(:x1, 1.0, 1.0, 0.5; label = "f1"),
    GaussianFactor(:x2, [2.0, -0.5], [1.0 0.0; 0.0 1.0], [1.0, 1.0]; label = "f2"),
    GaussianFactor(:x1, :x2, [1.0, 0.2], [1.0 1.0 0.3; 0.5 0.2 1.0], 2.0; label = "f3"),
    GaussianFactor(:x2, :x3, [0.5, 0.1], [1.0 0.5 1.0; 0.3 1.0 0.4], 2.0; label = "f4"),
    GaussianFactor(:x3, :x1, 0.5, [1.0 -1.0], 0.6; label = "f5"),
]

graph = factorGraph(variables, factors)

The example graph contains a cycle, so it uses the general iterative schedule rather than the specialized tree schedule.

Sum-Product Moment Inference

The moment form runs sum-product Gaussian belief propagation and stores each message and marginal as a mean vector and covariance matrix. Create a moment-form inference state with moment, then use gbp! to run iterative updates.

Each iteration updates factor-to-variable messages, variable-to-factor messages, and the stored variable marginals. The result is a set of Gaussian marginals.

inference = moment(graph; mean = 0.0, covariance = 1e6)
gbp!(graph, inference; iterations = 50, tolerance = 1e-6)

The mean and covariance keywords define the default initial belief for variables created without their own initial mean or covariance. Scalar defaults are expanded to each variable dimension.

If iterations is omitted, gbp! runs at most 10 iterations. The iterations keyword always acts as the maximum number of iterations. The tolerance keyword is applied to maxMarginalChange. If tolerance is omitted, no early stopping is used.

Use marginalMean and marginalCovariance when only one field is needed. Use marginal when the full marginal object is needed, or marginals to return all stored variable marginals:

marginalMean(graph, inference, :x1)
marginalCovariance(graph, inference, :x1)

For interactive inspection, printMessages prints messages adjacent to one variable or factor, and printMarginal prints sum-product marginals.

Sum-Product Canonical Inference

The canonical form computes the same sum-product Gaussian marginals as the moment form, but represents messages with information vectors and precision matrices. Products of Gaussian messages are represented internally as sums of information vectors and precision matrices.

Create a canonical-form inference state with canonical, then use gbp! to run iterative updates:

inference = canonical(graph; mean = 0.0, covariance = 1e6)
gbp!(graph, inference; iterations = 50, tolerance = 1e-6)

Marginals can still be inspected as means and covariances with the same public lookup functions used for the moment form.

Min-Sum MAP Inference

The min-sum form computes MAP estimates. It is the negative-log quadratic form of Gaussian max-product belief propagation: factor potentials become least-squares costs, messages are quadratic costs, and variable beliefs are MAP estimates.

This form optimizes the most likely state instead of computing marginal covariances. The min-sum inference state stores QuadraticMessage objects, which represent quadratic costs rather than Gaussian marginals. Use moment or canonical when Gaussian marginals are needed.

Create a min-sum inference state with minsum, then use gbp! to run iterative updates:

inference = minsum(graph; mean = 0.0, covariance = 1e6)
gbp!(graph, inference; iterations = 50, tolerance = 1e-6)

The mean and covariance keywords define the default initial belief for variables created without their own initial mean or covariance. For minsum, this belief is converted to an initial quadratic cost message.

Each iteration updates factor-to-variable messages, variable-to-factor messages, and the stored variable MAP estimates. For minsum, the result is a set of MAP estimates.

The tolerance keyword is applied to maxEstimateChange.

Use estimate for one variable and estimates for all variables:

estimate(graph, inference, :x1)
estimates(graph, inference)

For interactive inspection, printMessages prints messages adjacent to one variable or factor, and printEstimate prints min-sum MAP estimates.

Manual Message Updates

Use the manual message functions when you want to control the iteration loop yourself. They run the same message-passing computation as gbp!, but split it into explicit message and result steps.

messages! runs one full message step: factor-to-variable messages and variable-to-factor messages. It does not recompute variable results by itself, so call marginals! for moment and canonical, or estimates! for minsum:

inference = canonical(graph)

for _ in 1:20
    messages!(graph, inference)
end

marginals!(graph, inference)
inference = minsum(graph)

for _ in 1:20
    messages!(graph, inference)
end

estimates!(graph, inference)

For directional control, call the factor-to-variable and variable-to-factor passes explicitly:

inference = canonical(graph)

for _ in 1:20
    factorToVariableMessages!(graph, inference)
    variableToFactorMessages!(graph, inference)
end

marginals!(graph, inference)

The directional functions expose the two message passes separately. They are useful when experimenting with custom schedules. For normal inference, gbp! is the simpler entry point.

Convergence Diagnostics

Use maxMessageChange to compare message states between two iterations. For stored variable results, use maxMarginalChange with moment or canonical, and maxEstimateChange with minsum.

inference = canonical(graph)

for _ in 1:100
    oldVariableMessages = deepcopy(inference.variableToFactor)
    oldFactorMessages = deepcopy(inference.factorToVariable)
    oldMarginals = deepcopy(inference.marginal)

    messages!(graph, inference)
    marginals!(graph, inference)

    messageDiff = maxMessageChange(graph, inference, oldVariableMessages, oldFactorMessages)
    marginalDiff = maxMarginalChange(graph, inference, oldMarginals)

    if messageDiff < 1e-6 && marginalDiff < 1e-6
        break
    end
end

The message change includes both factor-to-variable and variable-to-factor messages. Use maxFactorMessageChange or maxVariableMessageChange to inspect one direction.

Sequential Schedule

Sequential scheduling is the default update order for gbp! and messages!. Factor-to-variable messages are updated first, followed by variable-to-factor messages. Messages are updated in place, so later updates in the same pass can use values computed earlier in that pass.

You can request sequential scheduling explicitly with schedule = :sequential:

inference = moment(graph)
gbp!(graph, inference; iterations = 20, schedule = :sequential)

For a manual loop, call messages! directly. Sequential scheduling is the default:

inference = moment(graph)

for _ in 1:20
    messages!(graph, inference)
    marginals!(graph, inference)
end

For directional control, call the two sequential message passes directly:

inference = moment(graph)

for _ in 1:20
    factorToVariableMessages!(graph, inference)
    variableToFactorMessages!(graph, inference)
    marginals!(graph, inference)
end

Flooding Schedule

Flooding scheduling updates messages in a next-message buffer before committing them to the inference state. With schedule = :flooding, updates within a pass read from the old message arrays and are committed together.

Use gbp! with schedule = :flooding to run iterative inference with this update order:

inference = moment(graph)
gbp!(graph, inference; iterations = 20, schedule = :flooding)

For a manual flooding loop, pass the same schedule keyword to messages!:

inference = moment(graph)

for _ in 1:20
    messages!(graph, inference; schedule = :flooding)
    marginals!(graph, inference)
end

Flooding scheduling works with moment, canonical, and minsum inference states. The keyword form is the normal public entry point. Create a FloodingSchedule explicitly only for low-level messages! calls that need a schedule object:

inference = moment(graph)
schedule = floodingSchedule(graph, inference)

for _ in 1:20
    messages!(graph, inference, schedule)
    marginals!(graph, inference)
end

The returned schedule is mutable step state for the selected graph and inference object. Recreate it after changing graph topology.

There are no separate public flooding calls for the two message directions, because committing one direction before the other would change the flooding semantics.

Residual Scheduling

Residual scheduling recomputes directed messages and updates only those whose new values differ most from their current values. This can reduce work on loopy graphs where a small subset of messages dominates the current error.

Use gbp! with schedule = :residual to run a complete residual-scheduled loop:

inference = moment(graph)
gbp!(graph, inference; iterations = 50, schedule = :residual, updateFraction = 0.2)

The updateFraction keyword controls the fraction of directed messages updated in each residual step. Use updateCount when you want a fixed number of largest-residual messages:

inference = moment(graph)
gbp!(graph, inference; iterations = 50, schedule = :residual, updateCount = 5)

For a manual residual loop, pass the same residual schedule keywords to messages!:

inference = moment(graph)

for _ in 1:20
    messages!(graph, inference; schedule = :residual, updateFraction = 0.1)
    marginals!(graph, inference)
end

Residual scheduling works with moment, canonical, and minsum inference states. The keyword form is the normal public entry point. Create a ResidualSchedule explicitly when you want to inspect or reuse the selected low-level schedule object:

inference = moment(graph)
schedule = residualSchedule(graph, inference; updateFraction = 0.1)

for _ in 1:20
    messages!(graph, inference, schedule)
    marginals!(graph, inference)
end

The residual schedule object stores mutable step state for the selected graph and inference object. Recreate it after changing graph topology or replacing the inference object.

There are no separate public residual calls for complete factor-to-variable or variable-to-factor passes, because each residual step selects individual directed messages.

Broadcast Message Computation

The broadcast keyword selects grouped message computation for moment, canonical, and minsum. Pass it to gbp! for a full inference run:

inference = moment(graph)
gbp!(graph, inference; iterations = 20, broadcast = true)

For a manual loop, pass the same keyword to messages!:

inference = moment(graph)

for _ in 1:20
    messages!(graph, inference; broadcast = true)
    marginals!(graph, inference)
end

For manual directional loops, pass broadcast = true to each message direction:

inference = moment(graph)

for _ in 1:20
    factorToVariableMessages!(graph, inference; broadcast = true)
    variableToFactorMessages!(graph, inference; broadcast = true)
    marginals!(graph, inference)
end

Grouped computation first accumulates all incoming contributions for a factor or variable. Each outgoing message is then formed by removing the contribution from the target edge.

This computation mode can be combined with sequential or flooding schedules. It is not used with residual scheduling, because residual scheduling selects individual directed messages by residual rather than running complete grouped message passes.

Damping

Damping blends a new factor-to-variable message with the previous message. It is often useful on loopy graphs where undamped message updates may oscillate.

Enable global damping through gbp!:

inference = minsum(graph)
gbp!(graph, inference; iterations = 50, damping = true, prob = 1.0, alpha = 0.35)

The alpha keyword is the weight of the previous message. The prob keyword is the probability that damping is applied to an eligible update.

Damping uses the same damping, prob, and alpha keywords with sequential, flooding, and residual schedules. It is applied to factor-to-variable message updates.

The same damping keywords can be used with the manual messages! API:

inference = canonical(graph)

for _ in 1:20
    messages!(graph, inference; damping = true, prob = 1.0, alpha = 0.35)
end

marginals!(graph, inference)

When running the two message directions manually, pass the damping keywords to factorToVariableMessages!:

inference = canonical(graph)

for _ in 1:20
    factorToVariableMessages!(graph, inference; damping = true, prob = 1.0, alpha = 0.35)
    variableToFactorMessages!(graph, inference)
end

marginals!(graph, inference)

Use dampEdges! to damp selected edges:

dampEdges!(graph, inference; variable = :x1, factor = "f3", alpha = 0.35)

Use undampEdges! to remove damping from selected edges:

undampEdges!(graph, inference; variable = :x1, factor = "f3")

Freezing Updates

Freezing keeps selected messages unchanged while the rest of the graph continues updating.

To freeze all outgoing messages from a factor or variable, use:

freezeFactor!(graph, inference, "f3")
freezeVariable!(graph, inference, :x2)

To freeze both message directions on one edge, use:

freezeEdge!(graph, inference; variable = :x1, factor = "f3")

Resume updates by unfreezing the same selections:

unfreezeFactor!(graph, inference, "f3")
unfreezeVariable!(graph, inference, :x2)
unfreezeEdge!(graph, inference; variable = :x1, factor = "f3")

Inspection helpers return booleans and use the same references:

isFrozenFactor(graph, inference, "f3")
isFrozenVariable(graph, inference, :x2)
isFrozenEdge(graph, inference; variable = :x1, factor = "f3")

Dynamic Graph Changes

Use addVariable! with an inference object when a new variable node must be added after inference has started. A new variable is usually followed by at least one new factor that connects it to the graph:

addVariable!(graph, inference, :x4, 1; label = "x4")
addFactor!(graph, inference, :x3, :x4, 0.4, [1.0 -1.0], 0.2; label = "f6")

gbp!(graph, inference; iterations = 50)

Passing the inference object makes this a warm-start update. Existing messages are preserved, and the message arrays are extended when new factor edges are added.

For moment and canonical, existing marginals are also preserved, and a new variable receives an initial belief from its own mean and covariance or from the inference defaults. For minsum, this belief is converted to an initial quadratic cost message and MAP estimate.

Warm-start topology updates extend only the inference object passed to addVariable! or addFactor!. Any other inference object created from the same graph before the topology change no longer matches the graph and should be recreated or updated separately.

Use updateFactor! when an existing factor's mean, coefficient, or covariance changes without changing graph topology:

updateFactor!(graph, inference; factor = "f2", mean = [1.8, -0.2], covariance = [0.1, 0.1])

gbp!(graph, inference; iterations = 50)

This reuses the existing inference state as a warm start. The message state still contains information from previous iterations, which is useful for dynamic inference. For an independent solve, update the graph and then create a fresh moment, canonical, or minsum object.

Because updateFactor! does not change graph topology, other inference objects created from the same graph still structurally match the graph. However, their messages have not been refreshed for the new factor parameters.