Lifted inference on transitive relations

摘要: Lifted inference algorithms are able to boost efficiency through exploiting symmetries of the underling first-order probabilistic models. Models with transitive relations (e.g., if X and Y friends so Z, then Z will likely be friends) essential in social network analysis. With n elements a relation model, computational complexity exact propositional is O(2n(n-1)/2), making it intractable for large domains. However, no tractable on has been reported relations. In this paper, we report novel deterministic approximate lifted algorithm, which efficiently solves problems without degenerating input We introduce an alternative graph representation models formulas homogeneous bivariate predicates. The new representation, closely related exponential-family random models, leads efficient lifting algorithm by asymptotic properties state space. perform experiments verify effectiveness proposed algorithm.