# An Inference Framework of Markov Logic Network for Link Prediction in Heterogeneous Networks
## 1 Introduction  
Link prediction (LP) in heterogeneous networks (also known as multi-relational LP) [1] aims to forecast multi-type connections between objects in networks. This field has recently garnered significant interest due to its diverse applications in social networks [2], knowledge graph completion [3], community discovery [4], item recommendation [5], etc. For instance, in a heterogeneous academic social network with entities like authors A, B, and C and link types such as _coauthor_ and _citedby_, as illustrated in Figure 1a, the LP task involves determining the validity of links like _coauthor_ (A, B), _citedby_ (A, B), and _citedby_ (B, C). Notably, these diverse link types mutually influence each other's existence, such as _citedby_ (C, D) impacting _coauthor_ (C, D). Moreover, the scarcity of observed links compared to potential links results in the link sparsity challenge. LP in heterogeneous networks faces two primary challenges. Firstly, nodes in such networks often exhibit multiple relationship types, necessitating the creation of a unified metric space that captures the inter-dependencies among these diverse links [6]. Current approaches [7, 8] typically extract and merge type-specific features into distinct metric spaces, aiming to enhance prediction performance through transfer learning or algebraic space integration. However, these methods often neglect dependencies across various link types, leading to decreased accuracy. For instance, the presence of a _coauthor_ link between C and D might influence _citedby_. Secondly, real-world networks exhibit sparsity,with numerous pairs of unconnected nodes. LP tasks, akin to supervised learning on non-relational data, involve predicting relational facts using known facts as supervision. This setup results in inadequate supervision and reduced accuracy in LP tasks. Addressing these challenges is crucial for effective multi-relational LP. Multi-type relations could be encompassed into logical formulas for inter-dependency calculation. Markov logic networks (MLNs) offer an intuitive methodology for delineating network relationships through logical formulas, garnering increasing acclaim in the domain of multi-relational link prediction [9]. MLNs permit deviations from formulas with a penalizing mechanism rather than outright failure, which aligns with the inherent uncertainty prevalent in real-world relationships among entities. The magnitude of the penalty is regulated by weights assigned to individual formulas, with higher weights denoting a more robust endorsement of the associated patterns. For instance, propositions such as \"coauthors are likely to be friends\" (\(coauthor(x,y)\to\text{friend}(x,y)\)) and \"if one author cites another, they might develop a friendly relationship\" (\(citedby(x,y)\to\text{friend}(x,y)\)) elucidate the interplay between different relations. By designing these formulas and employing grounding techniques, we can transform the information like \(citedby(\text{A},\text{C})\) into grounded predicates, which serve as nodes in the MLN structure. The inter-dependency between different relations can be represented through the weights of formulas, which are calculated using MLN's learning methods based on the values of MLN nodes. Similarly, the values of unknown nodes indicating link facts can be calculated through MLN's inference methods using these learned weights. In particular, LP in heterogeneous networks can be reformulated as an inference problem in MLNs and traditionally solved using Statistical Relational Learning (SRL) methods [10]. This approach predicts unknown links by inferring node labels in the MLN, using observed links as evidence, facing two major challenges for multi-relational LP: (1) the sparsity of observed links leads to numerous unobserved MLN nodes, and (2) the computational complexity of inference in large MLNs. Traditional SRL inference methods for MLNs struggle with these challenges due to their inability to efficiently handle latent variables in sparse network settings.