Секрет кривых узлов: как сравнить паутины экспресс
Графы считаются одинаковыми, если у них совпадает «рельеф». Две карты с горами и долинами: даже при разной прорисовке высоты и крутизна склонов могут быть теми же. Учёные превращают граф в миниатюрный ландшафт, где у каждой вершины своя кривизна — степень изгиба, подобная мере беспорядка в этой точке.
Алгоритм, как чуткий топограф, ощупывает рельеф. Он ищет вершины с одинаковой кривизной, используя анализ вибраций всей поверхности — словно ландшафт звенит на своих частотах. Метод не даёт ложных срабатываний: совпадение означает точное структурное равенство.
В основе лежат идеи математиков Джона фон Неймана и Эмми Нётер. Подобно тому как астрономы ищут тёмную материю по искривлению света, здесь изгибы ландшафта раскрывают скрытую структуру. В будущем это ускорит поиск лекарств (молекулы — это графы атомов) и сравнение нейросетей.
Оригинальная аннотация
как её написали авторы, на английском arXiv:2601.03787
Determining whether two graphs are structurally identical is a fundamental problem with applications spanning mathematics, computer science, chemistry, and network science. Despite decades of study, graph isomorphism remains a challenging algorithmic task, particularly for highly regular structures. Here we introduce a new algorithmic approach based on ideas from spectral graph theory and geometry that constructs candidate correspondences between vertices using their curvatures. Any correspondence produced by the algorithm is explicitly verified, ensuring that non-isomorphic graphs are never incorrectly identified as isomorphic. Although the method does not yet guarantee success on all inputs, we find that it correctly resolves every instance tested in deterministic polynomial time, including a broad collection of graphs known to be difficult for classical techniques. These results demonstrate that enriched spectral methods can be far more powerful than previously understood, and suggest a promising direction for the practical resolution of the complexity of the graph isomorphism problem.
Два графа одинакового строения, но разного рисунка называют изоморфными — от греческих слов «равный» и «форма».
В романе Нила Стивенсона «Анафем» учёные исследуют причудливые многомерные формы, чтобы понять устройство вселенной — игра с геометрией, созвучная этой задаче.