# An Inference Framework of Markov Logic Network for Link Prediction in Heterogeneous Networks
## 4 Proposed Method
### MLN-Based LP  
The labels of fact nodes in \(g^{i}\) could be determined through logical inference based on formulas rather than the VEM inference method. For instance, a grounding formula with a non-zero weight such as _citedby_\((A,B)\cap\textit{citedby}(A,C)\rightarrow\textit{citedby}(B,C)\) can create a true relation-node _citedby_\((B,C)\) if both _citedby_\((A,B)\) and _citedby_\((A,C)\) hold. By iteratively obtaining the joint distribution of unobserved node labels using Algorithm 2 based on the observed fact nodes in the substructures, more observed nodes can be acquired. A comparison with the joint distribution derived from logical formulas reveals an increasing discrepancy in VEM-based inferences as more unobserved fact nodes are updated to observed. Consequently, we opt to halt the iterative inferences when the difference surpasses a specified threshold, enabling the calculation of the joint distribution of \(V_{u}\) for LP tasks. Without loss of generality, we establish the KL divergence-based termination condition to determine whether further calculation should proceed by measuring the difference between the distribution of fact node labels obtained through logical evaluation and VEM-based methods:  
\[KL(P_{\text{f}}(U|V_{o}^{i})|P_{\epsilon}(U|V_{o}^{i})). \tag{14}\]  
Here, \(V_{o}^{i}\) denotes the observed fact nodes in \(g^{i}\), \(U\) represents the sole unobserved node in each formula, which can be evaluated logically as 1 or 0, corresponding to true or false, respectively. \(P_{\text{f}}\) signifies the value of \(U\) given \(V_{o}^{i}\) through logical evaluation, while \(P_{\epsilon}\) denotes the joint distribution from VEM-based inferences. A smaller KL divergence indicates that the two joint distributions calculated by VEM-based inferences and logical evaluations are more consistent. To calculate \(P_{\text{f}}(U|V_{o}^{i})\), we utilize Equation (12) to compute \(\mathbf{w}^{i}\), deriving the nonzero-weight formulas \(\mathcal{F}^{i}\) (\(\mathcal{F}^{i}\subset\mathcal{F}\)). Subsequently, we construct \(U\) using the fact nodes, whose labels could be logically inferred as true by \(\mathcal{F}^{i}\). Therefore, \(P_{\text{f}}(U|V_{o}^{i})\) could be redefined as \(P_{\text{f}}(U|V_{o}^{i},\mathcal{F}^{i})\). As \(P_{\epsilon}(U|V_{o}^{i})\) could be calculated using Algorithm 2 as \(\sum\limits_{n\in U}p_{\epsilon}(n)\), we transform Equation (14) into  
\[KL(P_{\text{f}}(U|V_{o}^{i})|P_{\epsilon}(U|V_{o}^{i})) \tag{15}\] \[= KL(P_{\text{f}}(U|V_{o}^{i},\mathcal{F}^{i})|\sum\limits_{n\in U }P_{\epsilon}(n))\] \[= \sum\limits_{n,n^{\prime}\in U,n^{\prime}\
eq n}p_{\text{f}}(n) \log\biggl{[}\frac{p_{\text{f}}(n)}{p_{\epsilon}(n^{\prime})}\biggr{]}.\]  
Equation (15) serves as the termination criterion, indicating that if it falls below a specified threshold, the computation in \(g^{i+1}\) continues. By this pause mechanism, we could prevent noisy data from causing significant error impacts. These concepts are consolidated in Algorithm 3. Within each substructure \(g^{i}(1\leq i\leq k)\), the time complexity of step 4 is \(O(|V_{g^{i}}|)\), where \(|V_{g^{i}}|\) denotes the average number of nodes in \(g^{i}\). Step 5's time complexity is \(O(T_{1}\cdot\mathcal{L}\cdot|E_{g^{i}}|)\) as per Algorithm 2, with \(|E_{g^{i}}|\) representing the average edge count in \(g^{i}\). The time complexity of steps 6 through 7 is \(O(|V_{g^{i}}|)\). Hence, in a scenario where \(T_{2}\) substructures are constructed, the time complexity of Algorithm 3 amounts to \(O(T_{2}\cdot(|V_{g^{i}}|+T_{1}\cdot\mathcal{L}\cdot|E_{g^{i}}|))\), where \(|E_{g^{i}}|\) and \(|V_{g^{i}}|\) are considerably smaller than \(|E|\) and \(|V|\), respectively. Specifically, the time complexity of substructure construction is \(O(T_{2}\cdot|V_{g^{i}}|)\), while the VEM-GCN integration exhibits a time complexity of \(O(T_{2}\cdot T_{1}\cdot\mathcal{L}\cdot|E_{g^{i}}|)\), respectively.