Hi,

You can first try to write a custom VertexProgram for belief propagation with Apache TinkerPop. A custom VertexProgram supports the massive message parsing needed for belief propagation.
If it works on TinkerPop you can use the same VertexProgram on JanusGraph (if a single TinkerPop machine does not suffice to hold your graph), but you will have the additional complexity of getting JanusGraph to work with Apache Spark.

A Google search on belief propagation VertexProgram TinkerPop does not give any relevant results.

Best wishes,    Marc