Sequence graphs realizations and ambiguity in language models

• URL: http://arxiv.org/abs/2402.08830v2
• Date: Fri, 11 Jul 2025 00:42:38 GMT
• Title: Sequence graphs realizations and ambiguity in language models
• Authors: Sammy Khalife, Yann Ponty, Laurent Bulteau,
• Abstract summary: Several popular language models represent local contexts in an input text $x$ as bags of words.<n>Some may be ambiguous, admitting several realizations as a sequence, while others may not admit any realization.<n>We study the realizability and ambiguity of sequence graphs from a and algorithmic point of view.
• Score: 1.3108652488669736
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Several popular language models represent local contexts in an input text $x$ as bags of words. Such representations are naturally encoded by a sequence graph whose vertices are the distinct words occurring in $x$, with edges representing the (ordered) co-occurrence of two words within a sliding window of size $w$. However, this compressed representation is not generally bijective: some may be ambiguous, admitting several realizations as a sequence, while others may not admit any realization. In this paper, we study the realizability and ambiguity of sequence graphs from a combinatorial and algorithmic point of view. We consider the existence and enumeration of realizations of a sequence graph under multiple settings: window size $w$, presence/absence of graph orientation, and presence/absence of weights (multiplicities). When $w=2$, we provide polynomial time algorithms for realizability and enumeration in all cases except the undirected/weighted setting, where we show the $\#$P-hardness of enumeration. For $w \ge 3$, we prove the hardness of all variants, even when $w$ is considered as a constant, with the notable exception of the undirected unweighted case for which we propose XP algorithms for both problems, tight due to a corresponding $W[1]-$hardness result. We conclude with an integer program formulation to solve the realizability problem, and a dynamic programming algorithm to solve the enumeration problem in instances of moderate sizes. This work leaves open the membership to NP of both problems, a non-trivial question due to the existence of minimum realizations having size exponential on the instance encoding.

Related papers

• A Polynomial-Time Algorithm for Variational Inequalities under the Minty Condition [79.18735797001183]
  Solving (Stampacchia) variational inequalities (SVIs) is a foundational problem at the heart of optimization.<n>We introduce a new variant of the ellipsoid algorithm wherein hyperplanes are obtained after taking a gradient descent step from the center of the ellipsoid.<n>We provide several extensions and new applications of our main results.
  arXiv  Detail & Related papers  (2025-04-04T13:24:41Z)
• Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
  Recently proposed quantum algorithm arXiv:2206.14999 is based on semidefinite programming (SDP) We generalize the SDP-inspired quantum algorithm to sum-of-squares. Our results show that our algorithm is suitable for large problems and approximate the best known classicals.
  arXiv  Detail & Related papers  (2024-08-14T19:04:13Z)
• Efficient Solution of Point-Line Absolute Pose [52.775981113238046]
  We revisit certain problems of pose estimation based on 3D--2D correspondences between features which may be points or lines. We show experimentally that the resulting solvers are numerically stable and fast.
  arXiv  Detail & Related papers  (2024-04-25T12:09:16Z)
• SAT-Based Algorithms for Regular Graph Pattern Matching [40.86962847131912]
  We propose a generalization of graph isomorphism that allows one to check complex structural properties. This specification is given in the form of a Regular Graph Pattern (ReGaP), a special type of graph inspired by regular expressions. We propose a SAT-based algorithm for checking if a target graph matches a given ReGaP.
  arXiv  Detail & Related papers  (2023-12-15T18:12:44Z)
• The Complexity of Envy-Free Graph Cutting [44.58084909019557]
  We consider the problem of fairly dividing a set of heterogeneous divisible resources among agents with different preferences. We focus on the setting where the resources correspond to the edges of a connected graph, and every agent must be assigned a connected piece of this graph. The problem is NP-complete, and we analyze its complexity with respect to two natural complexity measures: the number of agents and the number of edges in the graph.
  arXiv  Detail & Related papers  (2023-12-12T07:54:30Z)
• Distribution-Independent Regression for Generalized Linear Models with Oblivious Corruptions [49.69852011882769]
  We show the first algorithms for the problem of regression for generalized linear models (GLMs) in the presence of additive oblivious noise. We present an algorithm that tackles newthis problem in its most general distribution-independent setting. This is the first newalgorithmic result for GLM regression newwith oblivious noise which can handle more than half the samples being arbitrarily corrupted.
  arXiv  Detail & Related papers  (2023-09-20T21:41:59Z)
• Fast Maximum $k$-Plex Algorithms Parameterized by Small Degeneracy Gaps [30.06993761032835]
  The maximum $k$-plex problem is important but computationally challenging in applications such as graph mining and community detection. We present an exact algorithm parameterized by $g_k(G)$, which has the worst-case running time in the size of the input graph and exponential in $g_k(G)$. We further extend our discussion to an even smaller parameter $cg_k(G)$, the gap between the community-degeneracy bound and the size of the maximum $k$-plex.
  arXiv  Detail & Related papers  (2023-06-23T01:28:24Z)
• Discrete Graph Auto-Encoder [52.50288418639075]
  We introduce a new framework named Discrete Graph Auto-Encoder (DGAE) We first use a permutation-equivariant auto-encoder to convert graphs into sets of discrete latent node representations. In the second step, we sort the sets of discrete latent representations and learn their distribution with a specifically designed auto-regressive model.
  arXiv  Detail & Related papers  (2023-06-13T12:40:39Z)
• Compositional Generalization without Trees using Multiset Tagging and Latent Permutations [121.37328648951993]
  We phrase semantic parsing as a two-step process: we first tag each input token with a multiset of output tokens. Then we arrange the tokens into an output sequence using a new way of parameterizing and predicting permutations. Our model outperforms pretrained seq2seq models and prior work on realistic semantic parsing tasks.
  arXiv  Detail & Related papers  (2023-05-26T14:09:35Z)
• Linear-Time Modeling of Linguistic Structure: An Order-Theoretic Perspective [97.57162770792182]
  Tasks that model the relation between pairs of tokens in a string are a vital part of understanding natural language. We show that these exhaustive comparisons can be avoided, and, moreover, the complexity can be reduced to linear by casting the relation between tokens as a partial order over the string. Our method predicts real numbers for each token in a string in parallel and sorts the tokens accordingly, resulting in total orders of the tokens in the string.
  arXiv  Detail & Related papers  (2023-05-24T11:47:35Z)
• Can Language Models Solve Graph Problems in Natural Language? [51.28850846990929]
  Large language models (LLMs) are increasingly adopted for a variety of tasks with implicit graphical structures. We propose NLGraph, a benchmark of graph-based problem solving simulating in natural language.
  arXiv  Detail & Related papers  (2023-05-17T08:29:21Z)
• Non-Autoregressive Math Word Problem Solver with Unified Tree Structure [62.869481432887106]
  We propose a novel non-autoregressive solver, named textitMWP-NAS, to parse the problem and deduce the solution expression based on the unified tree. The results from extensive experiments conducted on Math23K and MAWPS demonstrate the effectiveness of our proposed MWP-NAS.
  arXiv  Detail & Related papers  (2023-05-08T08:53:37Z)
• The Subgraph Isomorphism Problem for Port Graphs and Quantum Circuits [0.0]
  We give an algorithm to perform pattern matching in quantum circuits for many patterns simultaneously. In the case of quantum circuits, we can express the bound obtained in terms of the maximum number of qubits.
  arXiv  Detail & Related papers  (2023-02-13T22:09:02Z)
• Casting graph isomorphism as a point set registration problem using a simplex embedding and sampling [0.0]
  A graph can be represented as a point set in enough dimensions using a simplex embedding and sampling. The isomorphism of them corresponds to the existence of a perfect registration between the point set forms of the graphs. The related idea of equivalence classes suggests that graph canonization may be an important tool in tackling graph isomorphism problem.
  arXiv  Detail & Related papers  (2021-11-15T12:16:21Z)
• Inferring Hidden Structures in Random Graphs [13.031167737538881]
  We study the two inference problems of detecting and recovering an isolated community of emphgeneral structure planted in a random graph. We derive lower bounds for detecting/recovering the structure $Gamma_k$ in terms of the parameters $(n,k,q)$, as well as certain properties of $Gamma_k$, and exhibit computationally optimal algorithms that achieve these lower bounds.
  arXiv  Detail & Related papers  (2021-10-05T09:39:51Z)
• The Generalized Mean Densest Subgraph Problem [30.33731479053404]
  We introduce a new family of dense subgraph objectives, parameterized by a single parameter $p$. Our objective captures both the standard densest subgraph problem and the maximum $k$-core as special cases. A major contribution of our work is analyzing the performance of different types of peeling algorithms for dense subgraphs both in theory and practice.
  arXiv  Detail & Related papers  (2021-06-02T02:58:35Z)
• Random Graph Matching with Improved Noise Robustness [2.294014185517203]
  We propose a new algorithm for graph matching under probabilistic models. Our algorithm recovers the underlying matching with high probability when $alpha le 1 / (log log n)C$. This improves the condition $alpha le 1 / (log n)C$ achieved in previous work.
  arXiv  Detail & Related papers  (2021-01-28T02:39:27Z)
• Adversarial Linear Contextual Bandits with Graph-Structured Side Observations [80.95090605985042]
  A learning agent repeatedly chooses from a set of $K$ actions after being presented with a $d$-dimensional context vector. The agent incurs and observes the loss of the chosen action, but also observes the losses of its neighboring actions in the observation structures. Two efficient algorithms are developed based on textttEXP3.
  arXiv  Detail & Related papers  (2020-12-10T15:40:07Z)
• Evolving test instances of the Hamiltonian completion problem [0.7734726150561086]
  We propose a new methodology to generate a diverse set of instances by using an evolutionary algorithm. We analyze the resulting graphs and get key insights into which attributes are most related to algorithm performance.
  arXiv  Detail & Related papers  (2020-10-05T20:04:58Z)
• Online Dense Subgraph Discovery via Blurred-Graph Feedback [87.9850024070244]
  We introduce a novel learning problem for dense subgraph discovery. We first propose a edge-time algorithm that obtains a nearly-optimal solution with high probability. We then design a more scalable algorithm with a theoretical guarantee.
  arXiv  Detail & Related papers  (2020-06-24T11:37:33Z)
• Can Graph Neural Networks Count Substructures? [53.256112515435355]
  We study the power of graph neural networks (GNNs) via their ability to count attributed graph substructures. We distinguish between two types of substructure counting: inducedsubgraph-count and subgraphcount-count, and both positive and negative answers for popular GNN architectures.
  arXiv  Detail & Related papers  (2020-02-10T18:53:30Z)

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.