Lifting Factor Graphs with Some Unknown Factors: The Colour Passing Algorithm

Table of Links

Abstract and 1. Introduction

2. Preliminaries and 2.1 Factor Graphs and Parameterised Factor Graphs

   2.2 The Colour Passing Algorithm

3. The LIFAGU Algorithm

4. Empirical Evaluation

5. Conclusion, Acknowledgements, and References

2.2 The Colour Passing Algorithm

The CP algorithm [1,7] constructs a lifted representation for an FG where all factors are known. As LIFAGU generalises CP, we briefly recap how the CP algorithm works. The idea is to find symmetries in an FG based on potentials of factors, ranges and evidence of randvars, as well as on the graph structure. Each randvar is assigned a colour depending on its range and evidence, meaning that randvars with identical ranges and identical evidence are assigned the

same colour, and each factor is assigned a colour depending on its potentials, i.e., factors with the same potentials get the same colour. The colours are then passed from every randvar to its neighbouring factors and vice versa. Passing colours around is repeated until the groupings of identical colours do not change anymore. In the end, randvars and factors, respectively, are grouped together based on their colour signatures.

Figure 3 depicts the procedure of the CP algorithm on a simple FG. The two factors ϕ1 and ϕ2 share identical potentials in this example. As all three randvars are Boolean and there is no evidence available, A, B, and C are assigned the same colour (e.g., green). Furthermore, the potentials of ϕ1 and ϕ2 are identical, so they are assigned the same colour (e.g., purple). The colours are then passed from randvars to factors: ϕ1 receives two times the colour green from A and B and ϕ2 receives two times the colour green from B and C. Afterwards, ϕ1 and ϕ2 are recoloured according to the colours they received from their neighbours. Since both ϕ1 and ϕ2 received the same colours, they are assigned the same colour during recolouring (e.g., purple). The colours are then passed from factors to randvars. During this step, not only the colours are shared but also the position of the randvars in the argument list of the corresponding factor. Thus, A receives a tuple (purple, 1) from ϕ1, B receives (purple, 2) from ϕ1 and (purple, 2) from ϕ2, and C receives (purple, 1) from ϕ2. Building on these new colour signatures, the randvars are recoloured such that A and C receive the same colour while B is assigned a different colour. Iterating the colour passing procedure does not change these groupings and thus we obtain the PFG shown on the right in Fig. 3.

When facing a situation with unknown factors being present in an FG, the CP algorithm cannot be applied to construct a lifted representation for the FG. In the upcoming section, we introduce the LIFAGU algorithm which generalises the CP algorithm and is able to handle the presence unknown factors.