Efficient Realisation of Advanced Colour Passing

This repository contains the source code of the advanced colour passing algorithm, where its subroutines to detect commutative and exchangeable factors, respectively, are efficiently realised.

The implementation is based on the following publications:

• Malte Luttermann, Tanya Braun, Ralf Möller, and Marcel Gehrke. Colour Passing Revisited: Lifted Model Construction with Commutative Factors. AAAI 2024.
• Malte Luttermann, Johann Machemer, and Marcel Gehrke. Efficient Detection of Exchangeable Factors in Factor Graphs. FLAIRS 2024.
• Malte Luttermann, Johann Machemer, and Marcel Gehrke. Efficient Detection of Commutative Factors in Factor Graphs. PGM 2024.
• Malte Luttermann, Ralf Möller, and Marcel Gehrke. On the Detection of Commutative Factors in Factor Graphs: Necessary and Sufficient Conditions. arXiv preprint.

Our implementation uses the Julia programming language.

Computing Infrastructure and Required Software Packages

All experiments were conducted using Julia version 1.11.2 together with the following packages:

• BenchmarkTools v1.8.0
• Combinatorics v1.1.0
• Dates v1.11.0
• Multisets v0.4.6
• OrderedCollections v2.0.0
• Random v1.11.0
• Serialization v1.11.0
• Statistics v1.11.1
• StatsBase v0.34.11

Moreover, we use openjdk version 11.0.20 to run the (lifted) inference algorithms, which are integrated via instances/ljt-v1.0-jar-with-dependencies.jar.

Instance Generation

First, the input instances must be generated. To do so, run julia instance_generator.jl all in the src/ directory. The input instances are then written to instances/input/intra (these are the instances for experiments regarding commutative factors) and to instances/input/inter (these are the instances for experiments regarding exchangeable factors).

Running the Experiments

After the instances have been generated, the experiments can be started by running julia run_eval.jl all in the src/ directory. The (lifted) inference algorithms are then directly executed by the Julia script. All results are written into the results/ directory.

To create the plots, run julia prepare_offline_plot.jl in the results/ directory to combine the obtained run times into averages and afterwards execute the R script plot-offline-diss.r (also in the results/ directory). The R script will then create a bunch of .tex files in the results/ directory containing the plots of the experiments. To obtain plots in .pdf format, change use_tikz = TRUE to use_tikz = FALSE in line 7 of plot-offline-diss.r before running it.