The Weighted First-Order Model Counting Problem (WFOMC) asks to compute the weighted sum of models of a given first-order logic sentence over a given domain. Conditioning WFOMC on evidence—fixing the truth values of a set of ground literals—has been shown impossible in time polynomial in the domain size (unless ♯P ⊆ FP) even for fragments of logic that are otherwise tractable for WFOMC without evidence. In this work, we address the barrier by restricting the binary evidence to the case where the underlying Gaifman graph has bounded treewidth. We present a polynomial-time algorithm in the domain size for computing WFOMC for the two-variable fragments ??² and ?² conditioned on such binary evidence. Furthermore, we show the applicability of our algorithm in combinatorial problems by solving the stable seating arrangement problem on bounded-treewidth graphs of bounded degree, which was an open problem. We also conducted experiments to show the scalability of our algorithm compared to the existing model counting solvers.

The Weighted First-Order Model Counting Problem (WFOMC) asks to compute the weighted sum of models of a given first-order logic sentence over a given domain. It can be solved in time polynomial in the domain size for sentences from the two-variable fragment with counting quantifiers, known as $C^2$. This polynomial-time complexity is known to be retained when extending $C^2$ by one of the following axioms: linear order axiom, tree axiom, forest axiom, directed acyclic graph axiom or connectedness axiom. An interesting question remains as to which other axioms can be added to the first-order sentences in this way. We provide a new perspective on this problem by associating WFOMC with graph polynomials. Using WFOMC, we define Weak Connectedness Polynomial and Strong Connectedness Polynomials for first-order logic sentences. It turns out that these polynomials have the following interesting properties. First, they can be computed in polynomial time in the domain size for sentences from $C^2$. Second, we can use them to solve WFOMC with all of the existing axioms known to be tractable as well as with new ones such as bipartiteness, strong connectedness, having $k$ connected components, etc. Third, the well-known Tutte polynomial can be recovered as a special case of the Weak Connectedness Polynomial, and the Strict and Non-Strict Directed Chromatic Polynomials can be recovered from the Strong Connectedness Polynomials.

Knowledge compilation transforms logical theories into circuit representations that support efficient reasoning. We study this problem for propositional groundings of FO², the two-variable fragment of first-order logic over finite domains. Given an FO² sentence and a domain of size n, its grounding yields a propositional theory over ground atoms. We ask whether such theories admit compact representations in DNNF-based and related knowledge compilation languages, and whether these can be constructed efficiently, both with respect to the domain size n for a fixed sentence. We show first that compact compilation is impossible in general: there exists an FO² sentence whose grounding over a domain of size n requires DNNF size 2^Ω(n). On the positive side, we develop a two-stage compiler that exploits the symmetries inherent in the propositional groundings of FO² sentences. It branches on unary and binary types rather than individual ground atoms, in a similar spirit to lifted inferences for probabilistic relational models. Moreover, it optimizes the compilation process by efficiently identifying and caching residual subproblems that are equivalent with respect to future extensions. Experiments show the practical efficiency of our approach, which often produces smaller circuits and compiles faster than straightforward grounding-based baselines.

We investigate lifted inference on ordered domains with predecessor relations, where the elements of the domain respect a total (cyclic) order, and every element has a distinct (clockwise) predecessor. Previous work has explored this problem through weighted first-order model counting (WFOMC), which computes the weighted sum of models for a given first-order logic sentence over a finite domain. In WFOMC, the order constraint is typically encoded by the linear order axiom introducing a binary predicate in the sentence to impose a linear ordering on the domain elements. The immediate and second predecessor relations are then encoded by the linear order predicate. Although WFOMC with the linear order axiom is theoretically tractable, existing algorithms struggle with practical applications, particularly when the predecessor relations are involved. In this paper, we treat predecessor relations as a native part of the axiom and devise a novel algorithm that inherently supports these relations. The proposed algorithm not only provides an exponential speedup for the immediate and second predecessor relations, which are known to be tractable, but also handles the general k-th predecessor relations. The extensive experiments on lifted inference tasks and combinatorics math problems demonstrate the efficiency of our algorithm, achieving speedups of a full order of magnitude.

We study the model enumeration problem of the function-free, finite domain fragment of first-order logic with two variables (FO2). Specifically, given an FO2sentence Γ and a positive integer n, how can one enumerate all the models of Γ over a domain of size n? In this paper, we devise a novel algorithm to address this problem. The delay complexity, the time required between producing two consecutive models, of our algorithm is quadratic in the given domain size n (up to logarithmic factors) when the sentence is fixed. This complexity is almost optimal since the interpretation of binary predicates in any model requires at least Ω(n2) bits to represent.

We consider the task of weighted first-order model counting (WFOMC), a fundamental problem of probabilistic inference in statistical relational learning. The goal of WFOMC is to compute the weighted sum of models of a given first-order logic sentence over a finite domain, where each model is assigned a weight by a pair of weighting functions. Past work has shown that WFOMC can be solved in polynomial time in the domain size if the sentence is in the two-variable fragment of first-order logic (FO2). This result is later extended to the case where the sentence is in FO2with the linear order axiom, which requires a binary predicate in the sentence to introduce a linear ordering of the domain elements. However, despite its polynomial theoretical complexity, the existing domain-liftable algorithm for WFOMC with the linear order often suffers from inefficiencies when applied to real-world problems. This paper introduces a novel domain-lifted algorithm for WFOMC with the linear order axiom. Compared to the existing approach, our proposed algorithm exploits the inherent symmetries within first-order logic sentences and weighting functions to minimize redundant computations. Experimental results verify the efficiency of our approach, demonstrating a significant speedup over the existing approach.

In this paper, we study the sampling problem for first-order logic proposed recently by Wang et al.—how to efficiently sample a model of a given first-order sentence on a finite domain? We extend their result for the universally-quantified subfragment of two-variable logic FO2(UFO2) to the entire fragment of FO2. Specifically, we prove the domain-liftability under sampling of FO2, meaning that there exists a sampling algorithm for FO2that runs in time polynomial in the domain size. We then further show that this result continues to hold even in the presence of counting constraints, such as ∀x∃=ky : φ(x, y) and ∃=kx∀y : φ(x, y), for some quantifier-free formula φ(x, y). Our proposed method is constructive, and the resulting sampling algorithms have potential applications in various areas, including the uniform generation of combinatorial structures and sampling in statistical-relational models such as Markov logic networks and probabilistic logic programs.

Given a first-order sentence ? and a domain size n, how can one sample a model of ? on the domain {1, . . . , n} efficiently as n scales? We consider two variants of this problem: the uniform sampling regime, in which the goal is to sample a model uniformly at random, and the symmetric weighted sampling regime, in which models are weighted according to the number of groundings of each predicate appearing in them. Solutions to this problem have applications to the scalable generation of combinatorial structures, as well as sampling in several statistical-relational models such as Markov logic networks and probabilistic logic programs. In this paper, we identify certain classes of sentences that are domain-liftable under sampling, in the sense that they admit a sampling algorithm that runs in time polynomial in n. In particular, we prove that every sentence of the form ∀x∀y: ?(x, y) for some quantifier-free formula ?(x,y) is domain-liftable under sampling. We then further show that this result continues to hold in the presence of one or more cardinality constraints as well as a single tree axiom constraint.

We study the problem of constructing the relational marginal polytope (RMP) of a given set of first-order formulas. Past work has shown that the RMP construction problem can be reduced to weighted first-order model counting (WFOMC). However, existing reductions in the literature are intractable in practice, since they typically require an infeasibly large number of calls to a WFOMC oracle. In this paper, we propose an algorithm to construct RMPs using fewer oracle calls. As an application, we also show how to apply this new algorithm to improve an existing approximation scheme for WFOMC. We demonstrate the efficiency of the proposed approaches experimentally, and find that our method provides speed-ups over the baseline for RMP construction of a full order of magnitude.

In this paper, we study the problem of recommending the appropriate datasets for authors, which is implemented to infer the proximity between authors and datasets by leveraging the information from a three-layered network, composed by authors, papers and datasets. To link author-dataset semantically by taking advantage of the rich content information of papers in the intermediate layer, we design an attentive and aggregate multi-layer network learning model. The aggregation is for integrating the intra-layer information of paper content and citations, while the attention is used for coordinating authors at the top-layer and datasets at the bottom-layer in the semantic space learned from papers in the intermediate layer. The experimental study demonstrates the superiority of our method compared with the solutions that extend existing models to our problem.

Network embedding, also known as graph representation, is a classical topic in data mining. It has been widely used in real-world network applications such as node classification and community detection. However, it remains open to find a method that is scalable and preserves both structure and content information. Based on generative adversarial networks, we propose an unsupervised network embedding framework NEGAN, which is featured by combining graph topology and node content. In NEGAN, network nodes are mapped to the target space in a highly flexible non-linear way, guided by the content of the nodes. This mapping is learned from the generator of the generative adversarial networks, and node adjacency in the input network is preserved. Experiments on real datasets show that NEGAN outperforms all the existing methods on many scenarios including node classification, visualization and community detection tasks.

For mountain landslide, This paper proposes an intelligent early-warning system for landslides based on ZigBee network. It adopts Cortex-M3 architecture of the chip as the embedded core control processor to improve system integration, data processing capabilities, the ZigBee uses CC2530 as the hardware foundation to construct ZIGBEE wireless sensor network, and then uses GPRS as the technological manner to remotely convey data transmission and early warning information. The results show that the system is completely functional. And it has versatility and good scalability, can overcome the traditional monitoring method of single function which efficiency is low and cost is high, it can effectively achieve the landslide monitoring and prevention of the adverse geological conditions under the mountains.

Collaborative filtering (CF) aims to produce user specific recommendations based on other users' ratings of items. Most existing CF methods rely only on users' overall ratings of items, ignoring the variety of opinions users may have towards different aspects of the items. Using the movie domain as a case study, we propose a framework that is able to capture users' opinions on different aspects from the textual reviews, and use that information to improve the effectiveness of CF. This framework has two components, an opinion mining component and a rating inference component. The former extracts and summarizes the opinions on multiple aspects from the reviews, generating ratings on the various aspects. The latter component, on the other hand, infers the overall ratings of items based on the aspect ratings, which forms the basis for item recommendation. Our core contribution is in the proposal of a tensor factorization approach for the rating inference. Operating on the tensor composed of the overall and aspect ratings, this approach is able to capture the intrinsic relationships between users, items, and aspects, and provide accurate predictions on unknown ratings. Experiments on a movie dataset show that our proposal significantly improves the prediction accuracy compared with two baseline methods.

Abstract Virtual endoscopy is a technique to explore hollow organs and anatomical cavities using 3D medical imaging and computer graphics. In this paper, boundary model and local feature structure are used to realize tissue segmentation, and a new efficient algorithm is presented to solve path planning. As to real‐time processing, a frame in virtual endoscopy is divided into near viewpoint part and far viewpoint part based on volume data characteristics in our method. In the aspect of scene rendering, a ray casting algorithm based on the boundary voxel is proposed. Thus the voyage images can be rendered in real time with high quality in virtual endoscopy system by using these techniques. The experiments show that application results of our algorithm in tissue segmentation, path planning, scene rendering are better than other algorithms. Copyright © 2011 John Wiley & Sons, Ltd.