# An Inference Framework of Markov Logic Network for Link Prediction in Heterogeneous Networks
## 4 Proposed Method
### MLN Substructure Construction  
To compute the joint distribution \(P(V_{u})\) efficiently without navigating the extensive MLN search space, we divide \(G\) into \(k\) substructures, labeled as \(G=\{g^{i}|1\leq i\leq k\}\). Constructing \(g^{i}\) involves choosing unobserved nodes neighboring \(V_{o}^{i-1}\) in \(g^{i-1}\) (labeled as \(V_{u}^{i}\)) and progressively expanding through neighboring nodes in the MLN hop by hop, until adequate information is collected for label computation.  
Viewed from a heterogeneous network perspective, the 2-hop enclosing subgraph \(N_{2}(u,v)\) has been validated as containing adequate information for LP between entities \(u\) and \(v\) in the heterogeneous network \(H\), with minimal approximation errors [12]. This validation guarantees the rationale to leverage the 2-hop enclosing subgraph principle for the expansive refinement of \(V_{u}^{i-1}\) within \(G\), which encompasses the links in \(H\). To achieve this, we map \(N_{2}(u,v)\) to corresponding fact nodes in MLN. Assuming that \(N_{2}(u,v)\) includes \(\eta\) predicates for facts like \(coauthor(x,y)\), the analogous nodes in \(G\) to \(N_{2}(u,v)\) in \(H\) are denoted as follows:  
\[\begin{split}&\mathcal{N}^{*}(\tau(u,v))=\\ &\{r_{1}(u,x),r_{2}(u,x),\cdots,r_{\eta}(u,x)\}\\ &\cup\{r_{1}(v,x),r_{2}(v,x),\cdots,r_{\eta}(v,x)\},\end{split} \tag{3}\]  
where \(\tau(u,v)\) is the MLN node corresponding to the link between \(u\) and \(v\) in \(H\).  
In the context of MLN, Equation (3) comprises ample information for the calculation of node labels for \(\tau(u,v)\), guiding the exploration of \(\tau(u,v)\)'s neighbors through successive expansion hops. For convenience of expression, we use \(n\) and \(N_{h}(n)\) to denote \(\tau(u,v)\) and its neighbors in MLN, reached through \(h\) expansion hops, respectively. In particular, the expansion of the \(h\)-th hop is fulfilled by adding the neighbors of all the nodes in \(N_{h-1}(n)\) iteratively. The expansion of \(V_{o}^{i-1}\) halts when all generated neighbors encompass the nodes specified in Equation (3).  
Note that without substructure construction, the interpretability of the entire MLN with respect to \(\mathbf{w}\) can be calculated based on \(P(V_{u})\). While our approach partitions the computation process, the substructure construction is specifically designed for the efficient estimation of \(P(V_{u})\). Consequently, despite this division, the weights \(\mathbf{w}\) can still be derived through conditional probability calculations, thus preserving the inherent interpretability of the original MLN.  
By this procedure of substructure construction, we could transform \(P(V_{u})\) into \(P(V_{u}^{1}\mid g^{1})\), \(P(V_{u}^{2}\mid g^{2})\), \(\ldots\), \(P(V_{u}^{k}\mid g^{k})\) (\(V_{u}^{i}\subset g^{i}\)) with minimal approximation errors. Consequently, this partition strategy reduces computational complexity from \(O(|E_{MLN}|\cdot T)\) to \(O(\sum_{i=1}^{k}|E_{g}^{i}|\cdot T_{i})\), where \(\sum_{i=1}^{k}|E_{g}^{i}|\ll|E_{MLN}|\) for typical sparse KGs. We summarize the steps of substructure construction in Algorithm 1 with time complexity \(O(k\cdot|V_{g}|)\), where \(|V_{g}|\) denotes the average number of fact nodes in substructures.