CS Paper Radar

RamseyGadgets: A Graph Construction Dataset for LLMs

Zohair Raza Hassan, Deepak Pandita

cs.CL cs.AI ·submitted 2026-08-15 03:15 UTC · v1
datasetcode/data

Abstract

Constructing special graphs is an important task within graph theory and computer science. Many popular graph constructions are the result of a comprehensive exploration of relevant graphs and human ingenuity. Given the rise of generative AI usage in mathematics, it is natural to test whether LLMs are able to construct graphs with specified properties using their reasoning capabilities. Unfortunately, many natural graph construction problems, such as finding extremal Ramsey-good graphs (i.e., avoiding specific monochromatic subgraphs), have been explored extensively in the literature, making it difficult to ascertain whether a construction is the product of an LLM's reasoning capabilities or its recollection from training data. In this work, we introduce \textbf{RamseyGadgets}, a novel dataset of 70 underexplored graph construction problems that require finding Ramsey-good graphs with special properties (e.g., containing an edge with a fixed color). These problems have reasonably sized solutions (at most 10 vertices) that can be verified by SAT solvers, making them suitable for automatic evaluation. Our dataset is easily expandable, as one can simply change the monochromatic subgraphs being avoided to obtain a new set of problems. We evaluate the performance of five open-source LLMs on our dataset and report the results. Our findings show that LLMs achieve only 37.70% accuracy on the hard-tier problems in our dataset, with Gemma-4-31B achieving the highest performance out of the five. We also showcase how our dataset allows us to ascertain what kind of hints help LLMs perform better at this task.

Closest papers

Nearest neighbours by meaning across the whole index.

AutoGrable: What Is a Good Graph for a Table?

cs.LG ·2026-08-11 ·Tamara Cucumides, Floris Geerts
similarity 0.70
Abstract · 28 pages, 4 figures

Graph learning presupposes a graph, and tables and relational databases do not come with one. Applying a GNN to them requires deciding which entities become nodes, which of them to connect, and through which relations---a decision made by hand, by schema heuristics, or by training a model on every candidate graph and keeping the best. We give a criterion that requires no trained graph model. In the minimal table-to-graph abstraction each row is a node, so a message-passing GNN, bounded by 1-WL, sees a construction only as a partition of the rows into colour-refinement classes: a construction is good for a task when that partition separates rows with different labels and does not split rows that share one. AutoGrable turns this criterion into a construction procedure. For incidence constructions the partition is fixed by the selected columns, so building a graph reduces to choosing them, and we score a candidate subset by a label-alignment risk: the held-out risk of the best predictor constant on its blocks, penalised by an occupancy term measuring how thinly the blocks are populated. The score materialises no graph and trains no GNN, so AutoGrable can search the space of subsets greedily and cheaply, and returns the resulting grable for single tables and for foreign-key schemas alike. Our experiments show that over a space of candidate graphs the score discards a large fraction while retaining the best; that AutoGrable recovers the columns that generate the label on controlled tasks and outperforms fixed, random, and task-aware constructors on real tasks under a fixed predictor; and that it is the only method compared that can decline to build a graph when none helps.

0.46

Graph determination problem from knowledge of its subgraphs

cs.CC cs.DS ·2026-10-12 ·Coralie Zens, Dominique Barth, Dimitri Watel, Marc-Antoine Weisser
theory similarity 0.67
Abstract

In the context of graph reconstruction studies, this paper addresses the problem defined as follows: given a sample of vertex-coloured graphs, each associated with a number, does there exist a connected graph containing exactly the given number of induced subgraphs isomorphic to each graph in the sample, such that every edge of the solution graph is included in at least one of these subgraphs. This paper first shows that this problem is $Σ$______-complete. The associated optimisation problem is to determine the minimum number of vertices in a solution graph, if one exists. For instances consisting of two paths, we prove NP-completeness in general and give a polynomial-time dynamic programming algorithm when one path is monochromatic.

0.26

GTA: Graph Theory Agent and Benchmark for Algorithmic Graph Reasoning with LLMs

cs.AI ·2026-09-10 ·Zixiang Xu, Yanbo Wang, Chenxi Wang, Lang Gao, Zirui Song +4 more
benchmarkcode/datahighly cited similarity 0.66
Abstract · 49 pages, 11 figures, including references and appendix

Large Language Models (LLMs) are increasingly asked to reason over structured data such as graphs, yet how reliably they can carry out multi-step graph algorithms in language remains unclear. Existing evaluations tend to use simple tasks on small graphs, to score code generation rather than reasoning over the graph itself, or to fix a single input format. We introduce Graph Theory Bench (GT Bench), a benchmark covering 24 classical graph problems in 44 task-structure settings, with over 100,000 examples across four representations: natural language, structured language, adjacency list, and adjacency matrix. Evaluating eight LLMs on GT Bench shows that accuracy is strongly tied to the input representation, that the best representation shifts with graph density, size, and topology as well as with the model, and that this sensitivity persists, attenuated, in the strongest reasoning models. Building on these observations, we propose the Graph Theory Agent (GTA), which pairs a preference-trained representation selector with plan-and-decompose scaffolding around a frozen executor LLM. GTA lifts Phi-4 from 53.5% to 69.1% on the benchmark's easy split and from 33.0% to 41.5% on its hard split, outperforming eight prompting and agent baselines, and transfers without retraining to GraCoRe and NLGraph. Code for benchmark generation and evaluation: https://github.com/xzx34/GTA. The project homepage is available at https://xzx34.github.io/gta/.

0.56

Scone: Symmetry-aware Neural Combinatorial Optimization for Graph Coloring

cs.LG ·2026-11-18 ·Paolo Pellizzoni, Melanie Weber
similarity 0.65
Abstract

Graph coloring, which entails assigning colors to nodes such that no adjacent nodes have the same color, is a fundamental combinatorial optimization problem. In general, however, finding a node coloring with no monochromatic edges given a fixed palette is NP-hard. This motivates learning-based methods that can learn to exploit recurring structure across instances to efficiently produce high-quality colorings. Crucially, the validity of a coloring is invariant to permutations of the colors, and we show that exploiting this symmetry reduces the size of the effective state space over which the model has to learn its policy. At the same time, the coloring algorithm must be able to break some symmetries, for example to assign different colors to two adjacent nodes belonging to the same automorphism orbit. In this paper, we introduce Scone, a model that uses a color-equivariant graph neural network to construct colorings sequentially, allowing information from previous assignments to propagate and break node symmetries. Scone achieves perfect solution quality with low inference times across several graph coloring tasks, including on sudoku_extreme and register allocations, and showcases generalization to graph families not encountered during training.

0.19

Ramsey Meets Simultaneous Planarity: Vertex Integrity and Pathwidth

cs.DS ·2026-10-12 ·Thomas Depian, Simon D. Fink, Alexander Firbas, Robert Ganian, Matthias Pfretzschner +1 more
theory similarity 0.65
Abstract · 32 pages, 8 figures

We study the following simultaneous embedding problem: Given k graphs on the same vertex set with the same pairwise intersection, do they admit planar drawings that coincide on their shared graph? We establish fixed-parameter tractability with respect to the vertex integrity of the union graph (that is, the union of the input graphs) plus k, resolving an open question and generalizing the known algorithm parameterized by vertex cover number plus k. Our main technical contribution on the way towards this result is the extension of the recently introduced Ramsey pruning technique beyond ordering problems. Finally, we complement our tractability result with a lower bound that establishes NP-hardness when both k and the pathwidth of the union graph are bounded by constants, ruling out a generalization of our main result to path- or treewidth.

0.31

When Vision Meets Graphs: A Survey on Graph Reasoning and Learning

cs.SI cs.CVcs.LG ·2026-09-03 ·Xinjian Zhao, Wei Pang, Zhixuan Yu, Xiangru Jian, Xiaozhuang Song +6 more
top venuesurveypositionhighly cited similarity 0.64
Abstract · IJCAI Survey Track, 2026

Graphs are a fundamental data structure underlying many problems in the natural and social sciences. Over the past decade, Graph Neural Networks (GNNs) have dominated graph machine learning, supported by solid theoretical foundations. Yet scientists often understand graph structure through vision: chemists read molecular diagrams and social scientists inspect network visualizations. Despite decades of work on graph visualization, most graph learning pipelines still treat graphs purely as symbolic structures, rarely leveraging the visual form of graphs. We argue that this gap deserves renewed attention in the era of powerful vision and vision-language models. This survey provides a first systematic overview of the emerging area we term vision meets graphs, which treats visual depictions of graphs as first-class inputs for reasoning and learning. We organize existing work into three threads. Vision for Graph Reasoning studies how models can use visual depictions of graphs to understand structure and carry out multi-step reasoning. Vision for Graph Learning explores how visual features can complement or augment graph encoders beyond known limitations of message passing. Scientific Graphs examines domains where standardized depiction conventions support both reasoning and learning. Our goal is to clarify what current methods can and cannot do, and to outline a path toward foundation models that perceive and reason about graphs as scientists do.

0.64

ClosureBench: A Constructive Benchmark for Compositional Graph Reasoning

cs.LG ·2026-08-18 ·Stefano Goria
benchmarkcode/data similarity 0.63
Abstract · 30 pages, 5 figures, 11 tables. Code and data: https://github.com/egolabs-ai/closurebench

Large language models fail on multi-step compositional reasoning, but measuring that failure is hard, because new models are trained on the benchmarks used to evaluate them. A fixed test set becomes a memorisation check soon after release. Constructive benchmarks avoid this by generating instances on demand. We introduce ClosureBench, a constructive benchmark for graph-relational logical reasoning. Each task is built from explicit primitives (reachability, degree, set operations, connectivity, aggregation), and its reference answer is computed by executing code that implements that logic exactly. Ground truth is therefore verified, and the supply of fresh instances is unlimited. The benchmark spans 26 task categories at three compositional levels, with three independent difficulty axes: graph size, edge density, and query depth. We evaluate models from 1.5B open weights to frontier systems (o3, GPT-4.1, Gemini 2.5, Claude Sonnet 4). Accuracy falls as graph size and query depth increase, and the two axes interact. The difficulty does not lie in the surface form, since it persists when the graph is given as a JSON edge list or an adjacency matrix rather than prose, nor in the reasoning rule, which models state correctly. It lies in carrying that rule out over the graph across many steps. A 4B model fine-tuned to emit verified programs instead of answers stays nearly flat across compositional levels, while every frontier model degrades. o3 falls from 96% on atomic queries to 82% on the most compositional; the 4B model holds at 93% at a fraction of the token cost. The program offloads multi-step execution to a runtime, and the model's remaining errors are almost entirely misread edges. Constructive generation also supports a direct memorisation check, comparing accuracy on seen and fresh instances.

0.26

Smallest Cubic Non-1-Planar Graphs

cs.CG math.COcs.DM ·2026-09-23 ·Sergey Pupyrev
similarity 0.63
Abstract

A graph is 1-planar if it has a drawing in which every edge is crossed at most once. We show that the smallest cubic non-1-planar graphs have $30$ vertices. Two such graphs are the Tutte-Coxeter graph of girth eight and a graph of girth seven that we call the Byte graph. Every subcubic graph with fewer than $30$ vertices is 1-planar. Our proof is computer-assisted, but directly testing all relevant graphs is impractical. To establish non-1-planarity of the two graphs, we extend a SAT-based solver with a custom clause propagator based on separating cycles and a case split based on graph automorphisms, allowing independent cases to be solved in parallel. To show that all smaller subcubic graphs are 1-planar, we introduce the concept of $k$-flexibility: every set of at most $k$ prescribed edges can remain uncrossed in some 1-planar drawing. We use this property to reconstruct 1-planar drawings of larger graphs from drawings of smaller $k$-flexible graphs. This replaces exhaustive testing of more than forty billion cubic graphs with computations on far fewer graphs of smaller order.

0.28