MPE does not return assignments for disconnected/isolated variables

[GiggleLiu]

Problem

When a probabilistic graphical model contains disconnected components or isolated variables (variables that don't appear in any pairwise/higher-order factors), the current MPE implementation does not include these variables in the returned assignment.

Example

Consider a model with:

• Variables: 0, 1, 2, 3
• Factors: f(0,1), f(1,2) (variable 3 is isolated)

Current behavior:

assignment = mpe(model)
# Returns: {0: x, 1: y, 2: z}  # Missing variable 3!

Expected behavior:

assignment = mpe(model)
# Returns: {0: x, 1: y, 2: z, 3: w}  # All variables included

Root Cause

The contraction tree only includes tensors that are connected through shared variables. Isolated variables with only unary factors are not contracted into the tree and thus their optimal assignments are never computed.

Potential Solutions

1. Post-processing: After contraction, identify variables not in the assignment and compute their optimal values from unary factors
2. Preprocessing: Add dummy binary factors with uniform potentials to connect isolated components
3. Separate handling: Detect disconnected components before contraction and solve each component separately

Discovered During

UAI benchmark testing - some benchmark models have isolated variables or disconnected components.

Related

PR #65 - Tropical einsum module with OMEinsum-style design