User 49 | 5/26/2014, 6:46:28 PM

Hi,

I was running Belief Propagation in GraphLab on a few public datasets (basically used test*cat*bool_joint). The results seem decent. However, I need to implement 'Lifted Belief Propagation' where I need to modify the message computation (the messages sent by variables to factors and vice versa). Could someone explain what code sequence to look at? And also, does GraphLab construct an explicit factor graph, i.e, one with variables and factors explicitly added with edges between them, or an implicit one (with only the variables, and potentials defined on the edges)?

Thanks!

User 140 | 5/27/2014, 5:27:39 PM

GraphLab allows the developer to specify a vertex type and an edge type as template parameters when defining a graphlab::distributed*graph. I defined these in src/graphlab/factors/bp*graph*data.h. The vertex program, which computes the messages, is defined in bp*vertex_program.hpp

bp*graph*data::vertex*data defines the vertex type, which stores the prior (sometimes referred to as potential) and belief distributions for a vertex. A vertex can define either a variable or a factor node---the difference between variables and factors is semantic. When declaring a variable node, it's distributions are always stored as a 1D dense*table (enforced by factor*graph.hpp). A factor node can have either a dense or sparse distribution (although if you are not using sparse tables, then you can ignore this). The only other difference between a variable and factor is an isVariable flag in vertex*data. This is simply used to make some things like logging easier.

The vertex program is run per vertex and essentially gathers all messages on the incoming edges (adding them in logspace with implicit broadcasting) in the Gather phase (bp*vertex*program::gather()). The Apply phase adds the vertex's prior distribution (bp*vertex*program::apply()). And the Scatter phase computes the outgoing messages which are put on the outgoing edges (bp*vertex*program::scatter()).

If you want to make a change to how the messages are computed, you would do it in bp*vertex*program (in scatter() probably).

-s

User 49 | 6/14/2014, 7:43:53 AM

Thank you.

Could you tell me where do I update edge properties? I want the edges in the factor graph (between variables and factors) to contain a new integer as its weight. I can pass it as an argument to the add*edge() call from make*bp*graph() in factor*graph.hpp. As far as I can see, it calls add*edge() in distributed*graph.hpp, which further calls add*edge() in distributed*ingress_base.hpp. But I cannot figure where to add the weight to the edge.

User 49 | 6/15/2014, 4:49:13 PM

Update: I got that thing cleared. You may ignore my previous comment.
I would like to what is the quantity 'const gather*type& total' in the function apply() in bp*vertex_program.hpp, and how and where is it computed? I need to use modify message passing so that each message gets raised to the corresponding 'edge weight'

User 140 | 6/16/2014, 7:36:22 PM

To answer what I think is your main question, in bp*vertex*program::scatter(...), you can just 'raise' new*message by your new weight (I would say after line 237 (cavity.table()->MAP(new*message);) and before regularization, but you can do it after that if you'd like). Be aware that the message is expected to be stored in log space, so raising a variable to a power is the equivalent of multiplication. Also, the shift*normalization() performed on new*message is not a true normalization but rather a shift in log space to preserve dynamic range.

To answer the rest of your question, gather*type is defined when you define the vertex program:
<pre><code>template<size*t MAX*DIM>
class bp*vertex*program :
public graphlab::ivertex*program< typename graph*type<MAX*DIM>::type,
factor*product<MAX*DIM>,
graphlab::messages::sum*priority > {
...
typedef typename ivertex*program*t::gather*type gather_type;
...
}
</code></pre>

In this case, factors/bp*vertex*program.hpp extends graphlab::ivertex*program, where ivertex*program is defined in vertex*program/ivertex*program.hpp:
<pre><code>template<typename Graph,
typename GatherType,
typename MessageType = graphlab::empty>
class ivertex*program { ...
typedef GatherType gather*type;
...
}
</code></pre>

So gather*type is of type factor*product<>, which is defined just above bp*vertex*program to wrap the operator+=(...) because graphlab expects gather_type to behave like the accumulator operator (+).

(For completeness, graph*type< >::type is defined in factors/bp*graph*data.h:
<pre><code>template<size*t MAX*DIM>
struct graph*type {
typedef graphlab::distributed*graph<vertex*data<MAX*DIM>, edge*data<MAX_DIM> > type;
};
</code></pre>
)

'gather*type& total' is computed by the iengine<>, which is an engine interface and part of core GraphLab. The only iengine I've looked at closely is the synchronous*engine in engine/synchronous*engine.hpp. synchronous*engine::execute*gathers(...) computes total and execute*applys(...) calls ivertex*program::apply(...) (bp*vertex_program::apply(...) in this case). However, you almost certainly do not want to modify core GraphLab.

User 334 | 10/1/2014, 5:37:01 AM

Hi there,

I have a quick question, that I cannot find out the answer by my self right now.

How is the variable evidence implemented? I mean, before running inference (using the belief propagation algorithm) you should set that some variables have some values ( you are saying that those variables are observed ones). How do we explicit that some variables are observed and have a specific value?

Thank you for your time

User 49 | 10/28/2014, 10:13:49 AM

Hi Breno,

I think one option that we have is that we can define singleton potentials (i.e, a single factor defined over a single variable). The values in its potential table would be according to the observed state of the variable. That is, if the variable was observed to be true, the entry under would be very high and vice versa.

Hope this helps.