Faster Lifting for Ordered Domains with Predecessor Relations

• URL: http://arxiv.org/abs/2507.19182v1
• Date: Fri, 25 Jul 2025 11:43:34 GMT
• Title: Faster Lifting for Ordered Domains with Predecessor Relations
• Authors: Kuncheng Zou, Jiahao Mai, Yonggang Zhang, Yuyi Wang, Ondřej Kuželka, Yuanhong Wang, Yi Chang,
• Abstract summary: We investigate lifted inference on ordered domains with predecessor relations.<n>Previous work has explored this problem through weighted first-order model counting.<n>We devise a novel algorithm that inherently supports these relations.
• Score: 18.987335996076556
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• Higher-Order Pattern Unification Modulo Similarity Relations [0.0]
  Combination of higher-order theories and fuzzy logic can be useful in decision-making tasks.<n>We adopt a more straightforward approach aiming at integrating two well-established and computationally well-behaved components.<n>We propose a unification algorithm for higher-order patterns modulo these similarity relations and prove its termination, soundness, and completeness.
  arXiv  Detail & Related papers  (2025-07-17T15:18:22Z)
• Sequential-Parallel Duality in Prefix Scannable Models [68.39855814099997]
  Recent developments have given rise to various models, such as Gated Linear Attention (GLA) and Mamba.<n>This raises a natural question: can we characterize the full class of neural sequence models that support near-constant-time parallel evaluation and linear-time, constant-space sequential inference?
  arXiv  Detail & Related papers  (2025-06-12T17:32:02Z)
• Preordering: A hybrid of correlation clustering and partial ordering [2.7651063843287718]
  We show that preordering remains NP-hard even for values in $-1,0,1$.<n>We introduce a linear-time $4$-approximation algorithm and a local search technique.
  arXiv  Detail & Related papers  (2025-02-20T13:12:03Z)
• Synthesising Recursive Functions for First-Order Model Counting: Challenges, Progress, and Conjectures [12.47276164048813]
  First-order model counting (FOMC) is a computational problem that asks to count the models of a sentence in finite-domain first-order logic. We relax the restrictions that typically accompany domain recursion to work with directed graphs that may contain cycles. These improvements allow the algorithm to find efficient solutions to counting problems that were previously beyond its reach.
  arXiv  Detail & Related papers  (2023-06-07T06:49:01Z)
• Weighted First Order Model Counting with Directed Acyclic Graph Axioms [7.766921168069532]
  Probabilistic inference and learning in many SRL can be reduced to Weighted First Model Counting (WFOMC) WFOMC is known to be intractable ($mathrm#P$ complete) We show that the fragment $mathrmC2$ with a Directed Acyclic Graph (DAG)exclusion, i.e., a axiomatized to represent axiom DAG, is domain liftable.
  arXiv  Detail & Related papers  (2023-02-20T08:35:13Z)
• General ordering theorem [0.0]
  We prove the General Ordering Theorem (GOT), which establishes a relation among any pair of orderings. We show that it acts on operators satisfying generic (i.e. operatorial) commutation relations. Remarkably, it establishes a formal relation between these two theorems, and it provides compact expressions for them, unlike the notoriously complicated ones currently known.
  arXiv  Detail & Related papers  (2023-02-02T17:49:35Z)
• Reinforcement Learning Based Query Vertex Ordering Model for Subgraph Matching [58.39970828272366]
  Subgraph matching algorithms enumerate all is embeddings of a query graph in a data graph G. matching order plays a critical role in time efficiency of these backtracking based subgraph matching algorithms. In this paper, for the first time we apply the Reinforcement Learning (RL) and Graph Neural Networks (GNNs) techniques to generate the high-quality matching order for subgraph matching algorithms.
  arXiv  Detail & Related papers  (2022-01-25T00:10:03Z)
• Near-Optimal Algorithms for Linear Algebra in the Current Matrix Multiplication Time [46.31710224483631]
  We show how to bypass the main open question of Nelson and Nguyen (FOCS, 2013) regarding the logarithmic factors in the sketching dimension for existing constant factor approximation oblivious subspace embeddings. A key technique we use is an explicit mapping of Indyk based on uncertainty principles and extractors. For the fundamental problems of rank computation and finding a linearly independent subset of columns, our algorithms improve Cheung, Kwok, and Lau (JACM, 2013) and are optimal to within a constant factor and a $loglog(n)$-factor, respectively.
  arXiv  Detail & Related papers  (2021-07-16T19:34:10Z)
• Higher-order Derivatives of Weighted Finite-state Machines [68.43084108204741]
  This work examines the computation of higher-order derivatives with respect to the normalization constant for weighted finite-state machines. We provide a general algorithm for evaluating derivatives of all orders, which has not been previously described in the literature. Our algorithm is significantly faster than prior algorithms.
  arXiv  Detail & Related papers  (2021-06-01T19:51:55Z)
• Better Regularization for Sequential Decision Spaces: Fast Convergence Rates for Nash, Correlated, and Team Equilibria [121.36609493711292]
  We study the application of iterative first-order methods to the problem of computing equilibria of large-scale two-player extensive-form games. By instantiating first-order methods with our regularizers, we develop the first accelerated first-order methods for computing correlated equilibra and ex-ante coordinated team equilibria.
  arXiv  Detail & Related papers  (2021-05-27T06:10:24Z)
• Extracting N-ary Cross-sentence Relations using Constrained Subsequence Kernel [36.86738081453646]
  We propose a new formulation of the relation extraction task where the relations are more general than intra-sentence relations. We propose a novel sequence representation to characterize instances of such relations. We evaluate our approach on three datasets across two domains: biomedical and general domain.
  arXiv  Detail & Related papers  (2020-06-15T07:23:58Z)
• Lagrangian Decomposition for Neural Network Verification [148.0448557991349]
  A fundamental component of neural network verification is the computation of bounds on the values their outputs can take. We propose a novel approach based on Lagrangian Decomposition. We show that we obtain bounds comparable with off-the-shelf solvers in a fraction of their running time.
  arXiv  Detail & Related papers  (2020-02-24T17:55:10Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.