Guiding Word Equation Solving using Graph Neural Networks (Extended Technical Report)

• URL: http://arxiv.org/abs/2411.15194v1
• Date: Tue, 19 Nov 2024 14:15:34 GMT
• Title: Guiding Word Equation Solving using Graph Neural Networks (Extended Technical Report)
• Authors: Parosh Aziz Abdulla, Mohamed Faouzi Atig, Julie Cailler, Chencheng Liang, Philipp Rümmer,
• Abstract summary: This paper proposes a Graph Neural Network-guided algorithm for solving word equations. The algorithm iteratively rewrites the first terms of each side of an equation, giving rise to a tree-like search space. Experiments are conducted on artificial and real-world benchmarks.
• Score: 0.0
• License:
• Abstract: This paper proposes a Graph Neural Network-guided algorithm for solving word equations, based on the well-known Nielsen transformation for splitting equations. The algorithm iteratively rewrites the first terms of each side of an equation, giving rise to a tree-like search space. The choice of path at each split point of the tree significantly impacts solving time, motivating the use of Graph Neural Networks (GNNs) for efficient split decision-making. Split decisions are encoded as multi-classification tasks, and five graph representations of word equations are introduced to encode their structural information for GNNs. The algorithm is implemented as a solver named DragonLi. Experiments are conducted on artificial and real-world benchmarks. The algorithm performs particularly well on satisfiable problems. For single word \mbox{equations}, DragonLi can solve significantly more problems than well-established string solvers. For the conjunction of multiple word equations, DragonLi is competitive with state-of-the-art string solvers.

Related papers

• LinSATNet: The Positive Linear Satisfiability Neural Networks [116.65291739666303]
  This paper studies how to introduce the popular positive linear satisfiability to neural networks. We propose the first differentiable satisfiability layer based on an extension of the classic Sinkhorn algorithm for jointly encoding multiple sets of marginal distributions.
  arXiv  Detail & Related papers  (2024-07-18T22:05:21Z)
• Ensemble Quadratic Assignment Network for Graph Matching [52.20001802006391]
  Graph matching is a commonly used technique in computer vision and pattern recognition. Recent data-driven approaches have improved the graph matching accuracy remarkably. We propose a graph neural network (GNN) based approach to combine the advantages of data-driven and traditional methods.
  arXiv  Detail & Related papers  (2024-03-11T06:34:05Z)
• NodeFormer: A Scalable Graph Structure Learning Transformer for Node Classification [70.51126383984555]
  We introduce a novel all-pair message passing scheme for efficiently propagating node signals between arbitrary nodes. The efficient computation is enabled by a kernerlized Gumbel-Softmax operator. Experiments demonstrate the promising efficacy of the method in various tasks including node classification on graphs.
  arXiv  Detail & Related papers  (2023-06-14T09:21:15Z)
• ComSearch: Equation Searching with Combinatorial Strategy for Solving Math Word Problems with Weak Supervision [21.249411371568236]
  We propose a novel search algorithm with strategy textbfComSearch, which can compress the search space by excluding mathematically equivalent equations. We investigate the noise in pseudo labels that hold wrong mathematical logic, which we refer to as the textitfalse-matching problem, and propose a ranking model to denoise the pseudo labels.
  arXiv  Detail & Related papers  (2022-10-13T13:25:22Z)
• GNNRank: Learning Global Rankings from Pairwise Comparisons via Directed Graph Neural Networks [68.61934077627085]
  We introduce GNNRank, a modeling framework compatible with any GNN capable of learning digraph embeddings. We show that our methods attain competitive and often superior performance compared with existing approaches.
  arXiv  Detail & Related papers  (2022-02-01T04:19:50Z)
• What's Wrong with Deep Learning in Tree Search for Combinatorial Optimization [8.879790406465556]
  We present an open-source benchmark suite for the NP-hard Maximum Independent Set problem, in both its weighted and unweighted variants. We also conduct an in-depth analysis of the popular guided tree search algorithm by Li et al. [NeurIPS 2018], testing various configurations on small and large synthetic and real-world graphs. We show that the graph convolution network used in the tree search does not learn a meaningful representation of the solution structure, and can in fact be replaced by random values.
  arXiv  Detail & Related papers  (2022-01-25T17:37:34Z)
• Learning by Fixing: Solving Math Word Problems with Weak Supervision [70.62896781438694]
  Previous neural solvers of math word problems (MWPs) are learned with full supervision and fail to generate diverse solutions. We introduce a textitweakly-supervised paradigm for learning MWPs. Our method only requires the annotations of the final answers and can generate various solutions for a single problem.
  arXiv  Detail & Related papers  (2020-12-19T03:10:21Z)
• Solving Arithmetic Word Problems by Scoring Equations with Recursive Neural Networks [25.08023032443234]
  Recent works use automatic extraction and ranking of candidate solution equations providing the answer to arithmetic word problems. In this work, we explore novel approaches to score such candidate solution equations using Tree-RNN configurations. Our proposed method consists of transforming the mathematical expression of the equation into an expression tree.
  arXiv  Detail & Related papers  (2020-09-11T19:48:42Z)
• Neural Subgraph Matching [57.05893848555512]
  NeuroMatch is an accurate, efficient, and robust neural approach to subgraph matching. NeuroMatch is 100x faster than existing geometric approaches and 18% more accurate than existing subgraph matching methods.
  arXiv  Detail & Related papers  (2020-07-06T22:06:38Z)
• Graph-to-Tree Neural Networks for Learning Structured Input-Output Translation with Applications to Semantic Parsing and Math Word Problem [33.610361579567794]
  We present a novel Graph-to-Tree Neural Networks, namely Graph2Tree consisting of a graph encoder and a hierarchical tree decoder, that encodes an augmented graph-structured input and decodes a tree-structured output. Our experiments demonstrate that our Graph2Tree model outperforms or matches the performance of other state-of-the-art models on these tasks.
  arXiv  Detail & Related papers  (2020-04-07T17:36:38Z)
• GLSearch: Maximum Common Subgraph Detection via Learning to Search [33.9052190473029]
  We propose GLSearch, a Graph Neural Network (GNN) based learning to search model. Our model is built upon the branch and bound bound, which selects one pair of nodes from the two input graphs to expand at a time. Our GLSearch can be potentially extended to solve many other problems with constraints on graphs.
  arXiv  Detail & Related papers  (2020-02-08T10:03:40Z)

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.