用神经符号方法自动发现图的代数构造,让抽象数据变可理解。
Neurosymbolic Discovery of Algebraic Graph Constructions
- 基于大模型与SageMath协作,逐轮推理并验证图的代数构造
- 在100个高度对称图上全部找到精确代数表达式,准确率100%
- 适合需要理解图结构本质的研究者,尤其擅长对称图分析
现有图搜索方法返回的是邻接矩阵或编码字符串,虽证明图存在,却无法揭示其结构特性。本文提出一种神经符号方法,仅凭原始数据自动发现简短代数描述,如凯莱图 $\mathrm{Cay}(Γ, S)$ 或字典积 $C_5[K_3]$。该方法在无需微调的大语言模型上运行,通过与计算机代数系统 SageMath 的交互,不断分析、假设并测试候选构造,直至匹配目标图。使用我们发布的模型上下文协议(MCP)服务器进行通信,匹配性由精确同构测试判定,确保结果可信。在包含100个二轨道对称图(最多25个顶点)的预设基准上,该代理成功为所有图找到验证过的代数构造,未依赖原始编码。模板枚举基线仅达约20%成功率,目录查找完全无效。当对称性降低时构造质量下降。作为应用,首次发现16个顶点的最小反例,推翻伯纳特-凯宁可分散性猜想。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。