Research map / Probabilistic and scientific modeling / Variational and generative sampling

Colour Passing Revisited: Lifted Model Construction with Commutative Factors

AAAI 2024 · Probabilistic and scientific modeling › Variational and generative sampling · approach: Exact inference for probabilistic programs · 4 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Proposes Advanced Colour Passing (CPR), a modified colour passing algorithm that exploits commutative factors via counting random variables (histograms) and detects identical factors independent of argument order, producing a lifted PFG independent of inference algorithm.

Problem

Lifted model construction from a propositional factor graph is bound to a specific inference algorithm (colour passing for lifted BP), ignores commutative factors, and fails to detect identical factors whose arguments are permuted, yielding poor compression.

Approach

Extends colour passing by omitting argument positions in messages for commutative factors, using histograms/counting random variables to detect commutative symmetries within factors and order-independent identical potentials between factors, followed by an offline step that introduces logical variables to yield a valid parfactor graph.

Key results

• CPR yields up to a factor 30 speedup in query time over CP for factor graphs with a single commutative factor.
• CPR achieves speedups of up to factor 25 over CP on factor graphs where about three percent of factors have permuted arguments.
• CPR's compression is unaffected by the percentage of permuted factors, whereas LVE on CP output becomes slower than VE at ten percent or more permuted factors.

Measured effects reported in the paper

Surprising findings

• LVE on the CP-produced model becomes slower than VE on the propositional factor graph when at least ten percent of factors have permuted argument lists.

Limitations

• Guarantees of correctness only for the domain-liftable fragment (at most two logvars per parfactor or at most one logvar per PRV).
• Worst-case exponential check over subsets of arguments for commutativity, though argued to be small in practice.
• Does not recursively search for additional count conversions in remaining argument lists.

Experimental setup

Datasets: synthetically generated factor graphs with commutative factors synthetically generated factor graphs with permuted-argument factors

Benchmarks: synthetic factor graphs with varying domain sizes

Metrics: average query time standard deviation of query time

Baselines: colour passing (CP) variable elimination (VE)

Builds on: colour passing lifted variable elimination count conversion lifted junction tree algorithm

Closest papers by meaning

• Lifted Hinge-Loss Markov Random Fields (AAAI 2019 · similarity 0.87)
• New Liftable Classes for First-Order Probabilistic Inference (NeurIPS 2016 · similarity 0.86)
• Lossless Compression of Structured Convolutional Models via Lifting (ICLR 2021 · similarity 0.84)
• On Lifted Inference Using Neural Embeddings (AAAI 2019 · similarity 0.84)
• A Generative Model of Symmetry Transformations (NeurIPS 2024 · similarity 0.84)
• Symmetry Guarantees Statistic Recovery in Variational Inference (NeurIPS 2026 · similarity 0.83)