# An Inference Framework of Markov Logic Network for Link Prediction in Heterogeneous Networks
## 3 Preliminaries  
Consider a heterogeneous network with the following components: \(\mathcal{V}\) represents the set of entities (e.g., papers, authors), \(\mathcal{R}\) denotes the set of edges representing relationships, and \(\mathcal{A}\) is the set of attributes associated with entities. We distinguish between observed and unobserved relationships where \(\mathcal{R}_{o}\) represents the set of observed relations and \(\mathcal{R}_{u}\) represents the set of unobserved relations. **Definition 1**. : _A heterogeneous network is defined as \(H=(\mathcal{R},\mathcal{V},\mathcal{A})\), where \(\mathcal{R}=\mathcal{R}_{o}\cup\mathcal{R}_{u}\) and \(|\mathcal{R}|+|\mathcal{V}|>2\)._To transform our heterogeneous network into an MLN, we first represent relationships as logical predicates. Each relationship becomes a predicate \(r(x,y)\), where \(r\) is a relation type from \(\mathcal{R}\), and \(x\) and \(y\) are entities from \(\mathcal{V}\). These predicates form the building blocks of logical formulas that capture patterns in our data. When we ground these formulas (replace variables with actual entities), we create fact nodes in MLN. For example, in the academic citation network like in Figure 1a, we might observe that when author A cites both authors B and C, authors B and C are likely to be related. This pattern can be encoded as a logical formula: _citedby_ (A, B) \(\wedge\)_citedby_ (A, C) \(\rightarrow\)_citedby_ (B, C), in which _citedby_ (A, B), _citedby_ (A, C) and _citedby_ (A, B) become concrete nodes in MLN. Let \(V\) represent all fact nodes in our MLN, consisting of \(V_{o}\) and \(V_{u}\), which denote the observed predicates (known relationships), and unobserved predicates (relationships to be inferred), respectively. Definition 2: An MLN is defined as \(M=\) (\(G\), \(\mathbf{w}\)), where the following are denoted:  
* \(G=(V,E)\) is an undirected graph where \(V\) is the set of fact nodes following Bernoulli distribution, \(E\) is the set of edges derived from logical formulas \(\mathcal{F}\). * The joint probability distribution over \(G\) is defined by \[P(V_{o},V_{u})=\frac{1}{Z(\mathbf{w})}\exp\left(\sum_{f\in\mathcal{F}}w_{f}n_{ f}(V_{o},V_{u})\right)\] where \(Z(\mathbf{w})\) is the partition function, \(w_{f}\) is the weight of formula \(f\), and \(n_{f}(\cdot)\) counts true groundings of \(f\). The parameters \(\mathbf{w}\) of an MLN can be learned through discriminative learning by maximizing the pseudo-likelihood of \(V_{o}\)[10]:  
\[\underset{\mathbf{w}}{\operatorname{argmax}}\sum_{n\in V_{o}}\log p(y_{n}| \operatorname{MB}(n)) \tag{1}\]  
where \(y_{n}\) represents the label of node \(n\), and \(\operatorname{MB}(n)\) refers to the Markov blanket of \(n\)[31], encompassing its direct parents, direct children, and other parents of its direct children within the MLN. The joint distribution \(P(V_{u})\) can be computed using maximum a posteriori (MAP) inference [26]:  
\[\underset{n\in V_{u}}{\operatorname{argmax}}\sum_{f\in F}w_{f}n_{f}(V_{o},V_{ u}) \tag{2}\]  
In this paper, we aim to address the multi-relational LP task within \(G\), by transforming \(H\) into \(G\) and calculating \(P(V_{u})\), where \(V_{u}\) is corresponding to unknown links in \(H\), and \(P(V_{u})\) represents the joint probability distribution. For the transformation, we firstly build \(G\) by establishing \(m\) formulas and the corresponding grounding. To address the efficiency bottleneck, we partition \(G\) into substructures \(\{g^{i}|1\leq i\leq k\}\), where \(V_{u}^{i}\) denotes the unobserved nodes in \(g^{i}\). To calculate \(P(V_{u}^{i})\) efficiently, we propose the VEM-based inference method to update \(\mathbf{w}\) by Equation (1) and calculate \(P(V_{u}^{i})\) by Equation (2) in each substructure \(g^{i}\). Moreover, we introduce a termination condition to determine the necessity of computations in \(g^{i+1}\). Consequently, we frame the inference of \(P(V_{u})\) into the computation of \(P(V_{u}^{1}\mid g^{1})\), \(P(V_{u}^{2}\mid g^{2})\),..., \(P(V_{u}^{k}\mid g^{k})\).