Learning Primality from Modular-Inverse Graphs
本文证明了 GraphSAGE 通过学习模逆图中的结构差异，能够以近乎完美的准确率区分质数与合数，而 GCN 则因其特定的消息传递限制而无法捕捉这些区别。
原始论文采用 CC BY 4.0 许可（https://creativecommons.org/licenses/by/4.0/）。 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。 阅读完整免责声明
数字是数学的基石，而在这些数字之中，素数占据着特殊的地位。素数是指大于一且只能被一和它本身整除的整数。可以被其他数字整除的数字被称为合数。几个世纪以来，数学家们一直在寻找高效的方法来区分这两类数字，这项任务对于现代密码学和计算机安全至关重要。虽然传统方法依赖于复杂的算术计算，但一种新的研究方向在探讨：机器是否可以通过将数字视为“形状”而非“数值”，从而学习识别这些模式。这种方法将数字内部隐藏的关系视为一张地图，希望这张地图的形状能够揭示数字本身的本质。
在最近的一项研究中，研究员塔尔·魏斯布拉特（Tal Weissblat）探索了人工智能是否可以通过检查这些数学地图，来学习区分素数与合数。研究员并没有将数字本身输入给计算机。相反，每个数字都被转换成了一个独特的图表，称为模逆图（modular-inverse graph）。为了创建这个图表，研究员选取一个特定的数字，并列出所有能由它构成的较小的整数。然后，如果两个较小的数字相乘所得的结果在除以原数后余数为一，研究员就在这对数字之间画一条线。这一规则被完全相同地应用于每一个数字，无论它是素数还是合数，且并未告知计算机哪类是哪类。其目标是观察生成的形状是否会根据数字类型的不同而呈现出自然的差异。
该研究首先对这些形状背后的理论进行了深入探讨。分析显示，素数的图表与合数的图表之间存在明显的结构差异。对于素数而言，其图表在特定的方式下是全连通的：除了零以外，每个点都至少与另一个点相连。这里不存在孤立漂浮的孤点。相比之下，合数的图表包含孤立点——即没有任何连接的数字。此外，素数产生的图表具有不同点之间最大可能的连接数，而合数的连接数较少，且存在那些额外的孤立点。这一理论发现表明，计算机只需通过计数连接数或寻找孤立点，就能分辨出两者的区别。
为了测试这一点，研究员利用包含 10,000 个整数（范围从 2 到 10,001）的数据集训练了两种不同类型的人工智能模型。数据经过划分，使模型在较小的数字上进行学习，随后在它们从未见过的较大的数字上进行测试。其中一种被称为 GraphSAGE 的模型旨在关注图中每个点的局部邻域。另一种被称为图卷积网络（Graph Convolutional Network）的模型则采用了不同的方法，即对邻居的信息进行平均。结果截然不同。GraphSAGE 模型以卓越的精度完成了任务，在未见的测试集中正确识别素数和合数的准确率接近 99.9%，它成功地将从小数字中学到的模式推广到了大得多的数字上。
然而，第二种模型却完全失败了。它的表现并不比随机猜测好，准确率恰好为 50%。理论分析解释了失败的原因。GraphSAGE 模型能够区分有连接的点和孤立的点，从而保留了素数图表中关键的结构差异。而另一种模型由于采用信息平均化的方式，抹平了这些差异。它将连接点和孤立点视为相同，从而有效地消除了区分素数与合数的关键特征。这种失败并非程序错误，而是该特定方法在应用于此类数学图时的根本性局限。
研究得出结论，从这些图表中学习素数性的能力完全取决于机器学习模型的架构。GraphSAGE 架构能够捕捉到素数微妙的结构特征，而另一种常见的架构则不能。研究还包括了一项检查，以确保模型确实是在利用图结构而非仅仅是在记忆数字。当移除图处理层时，模型的性能退回到了随机猜测水平。这证实了成功源于对连接形状的分析，而非任何隐藏的数值技巧。研究结果表明，算术属性确实可以编码进图结构中并被机器学习，前提是构建该机器时使用了能够识别这些差异的正确工具。
您所在领域的论文太多了？
获取与您研究关键词匹配的最新论文每日摘要——附技术摘要，使用您的语言。