Neurosymbolic Discovery of Algebraic Graph Constructions

• URL: http://arxiv.org/abs/2608.08118v1
• Date: Sat, 08 Aug 2026 13:07:51 GMT
• Title: Neurosymbolic Discovery of Algebraic Graph Constructions
• Abstract summary: We ask whether one can automatically discover a short algebraic description if only this raw data is provided.<n>We propose an agent that runs on a general-purpose large language model with no fine-tuning or per-target training.<n>We test the approach on a benchmark of 100 highly symmetric graphs.
• Score: 22.962110170304594
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: There are several methods for searching for graphs with prescribed properties, such as SAT solvers and specialized generators. These methods return the result as raw data: an adjacency matrix or a string encoding. The raw data certifies that the graph exists, but it does not reveal any structural properties of the graph. We ask whether one can automatically discover a short algebraic description if only this raw data is provided. We look for a description such as a Cayley graph $\mathrm{Cay}(Γ, S)$ or a lexicographic product $C_5[K_3]$. We address this question with a neurosymbolic approach. We propose an agent that runs on a general-purpose large language model with no fine-tuning or per-target training. The model interleaves reasoning with calls to the computer algebra system SageMath: it analyzes the target graph, proposes and tests candidate constructions, and revises them until the output matches the target. The agent communicates with SageMath through a Model Context Protocol (MCP) server, which we release as a general-purpose bridge. Whether a construction matches the target is checked by a single exact isomorphism test, and therefore rests on the symbolic side and not on the model. We test the approach on a benchmark of 100 highly symmetric graphs, namely two-orbit graphs on up to 25 vertices; the benchmark was fixed in advance. Our agent could find verified algebraic constructions for all of them, without falling back to raw encodings. A strong template-enumeration baseline reaches only about $20\%$, and a catalog lookup could not identify any of these graphs. However, construction quality declines when symmetry is removed. As a concrete application, we identify the smallest known counterexample to the Bernhart-Kainen dispersability conjecture, a $16$-vertex graph that enumeration found as raw data. For this graph, our agent found an explicit algebraic construction.

Related papers

• Agentic Graph Token Reasoning [10.837857911869035]
  We introduce agentic graph token reasoning, which recasts graph tokenization as part of the reasoning process itself.<n>We show that our models outperform a broad set of baselines by a large margin and transfer zero-shot to unseen domains without any per-target fine-tuning.
  arXiv  Detail & Related papers  (2026-08-01T08:56:26Z)
• SWING: Unlocking Implicit Graph Representations for Graph Random Features [57.956136773668476]
  We propose SWING: Space Walks for Implicit Network Graphs, a new class of algorithms for computations involving Graph Random Features on graphs.<n>We provide detailed analysis of SWING and complement it with thorough experiments on different classes of i-graphs.
  arXiv  Detail & Related papers  (2026-02-13T08:12:38Z)
• Learning from one graph: transductive learning guarantees via the geometry of small random worlds [8.781923502647055]
  We develop new concentration-of-measure tools that leverage the geometric regularities of large graphs via low-dimensional metric embeddings.<n>We establish two principal learning results. The first concerns arbitrary deterministic $k$-vertex graphs, and the second addresses random graphs that share key geometric properties with an ErdHos-R'enyi graph $mathbfG=mathbfG(k,p)$ in the regime $p in mathcalO((log (k)/k)1/2)
  arXiv  Detail & Related papers  (2025-09-08T17:13:28Z)
• Graph Inference with Effective Resistance Queries [2.2349172369559156]
  We study graph inference using an oracle that returns the effective resistance (ER) between a pair of vertices.<n>Although it is known that an $n$-vertex graph can be uniquely reconstructed from all possible ER queries, little else is known.
  arXiv  Detail & Related papers  (2025-02-25T16:37:25Z)
• Shedding Light on Problems with Hyperbolic Graph Learning [2.3743504594834635]
  We look at the field of hyperbolic graph representation learning.<n>We find that results do not diligently present baselines, make faulty modelling assumptions, and use misleading metrics.<n>We introduce a family of benchmark datasets to ascertain the applicability of (hyperbolic) graph neural networks.
  arXiv  Detail & Related papers  (2024-11-11T03:12:41Z)
• Universal graph representation of stabilizer codes [0.5097809301149342]
  We introduce a representation of stabilizer codes as graphs with certain structures.<n>This gives a new universal recipe for code construction by way of finding graphs with nice properties.<n>We use graphs in a probabilistic analysis to extend the quantum Gilbert-Varshamov bound into a three-way distance-rate-weight trade-off.
  arXiv  Detail & Related papers  (2024-11-07T18:58:58Z)
• Cayley Graph Propagation [0.0]
  Graph neural networks (GNNs) are notoriously vulnerable to over-squashing.<n>In this work, we show that truncation is detrimental to the coveted expansion properties.<n>We propose CGP, a method to propagate information over a complete Cayley graph structure.
  arXiv  Detail & Related papers  (2024-10-04T13:32:34Z)
• AnchorGAE: General Data Clustering via $O(n)$ Bipartite Graph Convolution [79.44066256794187]
  We show how to convert a non-graph dataset into a graph by introducing the generative graph model, which is used to build graph convolution networks (GCNs) A bipartite graph constructed by anchors is updated dynamically to exploit the high-level information behind data. We theoretically prove that the simple update will lead to degeneration and a specific strategy is accordingly designed.
  arXiv  Detail & Related papers  (2021-11-12T07:08:13Z)
• ExplaGraphs: An Explanation Graph Generation Task for Structured Commonsense Reasoning [65.15423587105472]
  We present a new generative and structured commonsense-reasoning task (and an associated dataset) of explanation graph generation for stance prediction. Specifically, given a belief and an argument, a model has to predict whether the argument supports or counters the belief and also generate a commonsense-augmented graph that serves as non-trivial, complete, and unambiguous explanation for the predicted stance. A significant 83% of our graphs contain external commonsense nodes with diverse structures and reasoning depths.
  arXiv  Detail & Related papers  (2021-04-15T17:51:36Z)
• Learning Sparse Graph Laplacian with K Eigenvector Prior via Iterative GLASSO and Projection [58.5350491065936]
  We consider a structural assumption on the graph Laplacian matrix $L$. The first $K$ eigenvectors of $L$ are pre-selected, e.g., based on domain-specific criteria. We design an efficient hybrid graphical lasso/projection algorithm to compute the most suitable graph Laplacian matrix $L* in H_u+$ given $barC$.
  arXiv  Detail & Related papers  (2020-10-25T18:12:50Z)
• Inverse Graph Identification: Can We Identify Node Labels Given Graph Labels? [89.13567439679709]
  Graph Identification (GI) has long been researched in graph learning and is essential in certain applications. This paper defines a novel problem dubbed Inverse Graph Identification (IGI) We propose a simple yet effective method that makes the node-level message passing process using Graph Attention Network (GAT) under the protocol of GI.
  arXiv  Detail & Related papers  (2020-07-12T12:06:17Z)
• Non-Parametric Graph Learning for Bayesian Graph Neural Networks [35.88239188555398]
  We propose a novel non-parametric graph model for constructing the posterior distribution of graph adjacency matrices. We demonstrate the advantages of this model in three different problem settings: node classification, link prediction and recommendation.
  arXiv  Detail & Related papers  (2020-06-23T21:10:55Z)
• Wasserstein-based Graph Alignment [56.84964475441094]
  We cast a new formulation for the one-to-many graph alignment problem, which aims at matching a node in the smaller graph with one or more nodes in the larger graph. We show that our method leads to significant improvements with respect to the state-of-the-art algorithms for each of these tasks.
  arXiv  Detail & Related papers  (2020-03-12T22:31:59Z)

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.