CayleyPy library

Name: CayleyPy library
Creator: CayleyPy project
Published: 2025-09-23T23:40:36+08:00

arXiv2025-09-23 更新2025-09-25 收录

图论

计算代数

数据链接：

https://github.com/cayleypy/cayleypy 数据链接链接失效反馈

官方服务：

资源简介：

CayleyPy 是一个开源的 Python 库，用于计算 Cayley 图和 Schreier 图。该库支持任意生成器，并提供内置支持 dozens 的已知 Cayley 图的 Sn、An 和矩阵组。CayleyPy 的重点是直接增长计算，通过有效的广度优先搜索算法，比标准计算机代数系统 GAP/SAGE 快 1000 倍。

CayleyPy is an open-source Python library for computing Cayley graphs and Schreier graphs. It supports arbitrary generators, and provides built-in support for dozens of well-known Cayley graphs corresponding to symmetric groups Sn, alternating groups An, and matrix groups. CayleyPy focuses on direct growth computation, leveraging efficient breadth-first search algorithms, and runs up to 1000 times faster than standard computer algebra systems such as GAP/SAGE.

提供机构：

CayleyPy project

创建时间：

2025-09-23

原始信息汇总

CayleyPy数据集概述

数据集简介

CayleyPy是一个基于人工智能的库，用于处理googol规模的大型图。支持Cayley图、Schreier陪集图等类型。

主要功能

支持机器学习/强化学习方法进行路径查找
直径和增长率估计
嵌入计算
小子图的高效BFS搜索
高效随机游走生成
高效束搜索
哈密顿路径查找
支持CPU、GPU、TPU高效计算（使用JAX），可在Kaggle上使用

数学应用

直径和增长率估计
词度量和扩散距离的近似计算
不同类型随机游走的混合时间估计
从给定状态进行BFS搜索（增长函数、邻接矩阵、最后一层）
图和生成器库（LRX、TopSpin、魔方、花环、地球仪等）
包含某些问题解决方案的数据集库

安装方式

推荐从GitHub安装最新版本： bash pip install git+https://github.com/cayleypy/cayleypy
也可使用pip安装（可能缺少最新功能）： bash pip install cayleypy

文档资源

最新版本的库文档（API参考）可在https://cayleypy.github.io/cayleypy-docs/api.html获取。

开发指南

开发环境设置

bash git clone https://github.com/cayleypy/cayleypy.git cd cayleypy pip install -e .[torch,lint,test,dev,docs]

测试与检查

运行所有测试（包括慢速测试）： bash RUN_SLOW_TESTS=1 pytest
提交前检查： bash ./lint.sh pytest
覆盖率检查： bash coverage run -m pytest && coverage html

代码规范

使用Black代码格式化工具
遵循Google Python风格指南
使用pylint检查强制执行样式规则

使用示例

基本用法

定义置换群和矩阵群的Cayley图
运行BFS搜索
获取显式Networkx图

计算功能

Cayley图谱计算
路径查找（束搜索、BFS）
增长函数计算（LX、TopSpin陪集）
性能基准测试（BFS版本比较、GPU基准测试）

模型支持

预测器模型

包含机器学习模型库，用于束搜索算法中的路径查找
可通过Predictor.pretrained轻松访问预训练模型
当前可用模型列表位于：https://github.com/cayleypy/cayleypy/blob/main/cayleypy/models/models_lib.py

模型架构

基于PyTorch神经网络
包含三部分：模型架构描述、超参数配置、模型权重
权重存储在Kaggle平台

项目来源

项目理念来源于Alexander Chervov
初始代码开发可见Kaggle数据集：https://www.kaggle.com/datasets/alexandervc/growth-in-finite-groups
参考论文：https://arxiv.org/abs/2502.18663, https://arxiv.org/abs/2502.13266

搜集汇总

数据集介绍

构建方式

CayleyPy数据集通过高效广度优先搜索算法构建，支持任意置换群和矩阵群的Cayley图计算。该库利用GPU加速技术，相比传统计算机代数系统GAP/SAGE，在计算速度和可处理图规模上提升达三个数量级。数据生成过程涵盖对称群Sn、交错群An及特殊矩阵群等数十种预定义生成元，通过系统化实验采集图的直径、增长向量等核心指标。

特点

该数据集的核心特征在于其数学严谨性与计算高效性的统一。一方面，它包含基于群论严格定义的Cayley图结构，覆盖置换群、幂零群等代数对象；另一方面，通过优化算法实现超大规模图处理能力，可支持高达10^40量级的群运算。数据内容涵盖图的直径分布、增长函数统计特征、谱性质等多维指标，并首次公开了约200个关于Cayley图直径拟多项式规律的新猜想。

使用方法

研究者可通过Python接口直接调用CayleyPy库进行图论计算，或基于其发布的Kaggle基准数据集开展路径规划算法验证。数据集支持三种典型应用场景：一是通过预定义生成元快速构建特定Cayley图；二是利用增长计算功能分析图的度量性质；三是结合强化学习框架求解群元素分解问题。所有实验数据均提供可复现的Jupyter Notebook，并包含与GAP系统的性能对比基准。

背景与挑战

背景概述

CayleyPy库作为计算数学与人工智能交叉领域的重要工具，于2025年由多国研究团队联合发布，旨在通过深度学习技术解决群论中凯莱图的路径搜索与增长计算问题。该项目继承并拓展了传统计算机代数系统（如GAP/Sage）的功能，专注于对称群、交错群及矩阵群的凯莱图计算，其核心研究目标是通过高效算法实现超大规模图结构的直径计算与生成元分解。该库的诞生标志着计算群论研究范式的转变，通过GPU加速技术将计算效率提升至传统方法的千倍量级，为数学猜想发现与验证提供了前所未有的计算平台。

当前挑战

在领域问题层面，凯莱图直径计算作为NP难问题，其复杂性体现在对称群Sn的直径上界优化（如Babai猜想中O(n²)边界的精细化证明）以及零幂群中增长分布的高斯性验证。构建过程中的技术挑战包括：其一，超大规模图结构的存储与遍历算法设计，需在有限内存下处理高达10^40量级的群元素；其二，生成元体系的通用性支持，需兼容置换群、矩阵群及生物信息学中的特殊生成器（如反转、转座子）；其三，人工智能方法与经典群论算法的融合，尤其在路径搜索的强化学习框架中，需解决训练数据生成与收敛性保证的平衡问题。

常用场景

经典使用场景

在群论与组合数学研究领域，CayleyPy library 作为专为凯莱图计算设计的开源Python工具库，其经典应用场景集中于高效执行广度优先搜索算法，以计算对称群Sn和交错群An等有限群的凯莱图直径与增长函数。该库通过GPU加速实现了比传统计算机代数系统GAP/Sage快三个数量级的计算速度，能够处理高达S15规模（约10^12个节点）的图结构。研究者通过预定义的百余种生成元集合（如Coxeter生成元、循环移位与对换组合LX/LRX等），系统分析图的层增长分布、最长路径特征及谱性质，为群论猜想验证提供大规模计算实验平台。

衍生相关工作

CayleyPy library 的发布催生了一系列衍生研究方向。基于其计算结果提出的“准多项式直径猜想”激发了群表示论与算法复杂性的交叉研究，如Douglas等人开发的扩散模型路径搜索方法。库中生成的Sheveleva2和Koltsov3对合生成元家族，为最大直径图构造提供了新模式。在人工智能领域，库支持的“LLM友好型猜想”将群元素分解问题转化为排序任务，形成CayleyBench基准测试集，用于评估大语言模型的数学推理能力。此外，库与Kaggle平台的集成推动了10余个公开挑战赛的设立，使凯莱图路径规划成为衡量强化学习算法性能的新标准。

数据集最近研究