Relational Markov Networks (RMN)

A relational Markov network (RMN) [9] is a model for data with relations and discrete attributes. It is specified by a set of clique templates ${\mathbf{C}}$ and corresponding potentials $\boldsymbol{\Phi}$. Using the example in the introduction, a model can be formed by defining a single clique template $C=(\mathrm{con}(A), \mathrm{knows}(A,B), \mathrm{con}(B))$ and the corresponding potential $\phi_C$ over ${\mathbf{x}}(C)$ which is (a subset of) the concatenation of attribute vectors ${\mathbf{x}}(\mathrm{con}(A))$, ${\mathbf{x}}(\mathrm{knows}(A,B))$, and ${\mathbf{x}}(\mathrm{con}(B))$. Given a relational database, the RMN produces an unrolled Markov network over all the attributes $\boldsymbol{X}$. The cliques $c \in C(\mathcal{I})$ instantiated by a template $C$ share the same clique potential $\phi_C$. The combined probabilistic model is $p(\boldsymbol{X}) = \frac{1}{Z} \prod_{C \in {\mathbf{C}}} \phantom{o} \prod_{c \in C(\mathcal{I})} \phi_C({\mathbf{x}}(c))$, where $Z$ is a normalisation constant and $C(\mathcal{I})$ contains all the instantiations of the template $C$. In general, a template can be any boolean formula over the relations.

The general inference task is to compute the posterior distribution over all the variables $\boldsymbol{X}$. The network induced by data can be very large and densely connected, so exact inference is often intractable [9]. The belief propagation (BP) algorithm [6] is guaranteed to converge to the correct marginal probabilities only for singly connected Markov networks, but it is used as a good approximation also in the loopy case. The learning task, or the estimation of the potentials $\boldsymbol{\Phi}$ is done using the maximum a posteriori criterion. It requires an iterative algorithm alternating between updating the parameters of the potentials and running the inference algorithm on the unrolled Markov network.