📊 statistics

Learning the Graphical Nature of Symmetries

This paper introduces a comprehensive dataset of over 131,000 Cayley graphs to investigate how finite group properties are encoded in graph geometry, yielding new enumerative sequences, empirical conjectures on structural regularities, and demonstrating that graph neural networks can effectively learn algebraic group characteristics directly from graph data.

Original authors: Rashid Barket, Enrico Grimaldi, Yacoub Hendi, Edward Hirst, Adam Onus, Harmeet Singh

Published 2026-07-15

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Rashid Barket, Enrico Grimaldi, Yacoub Hendi, Edward Hirst, Adam Onus, Harmeet Singh

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you have a massive library of secret codes, where each code is a "group" of symmetries—like the different ways you can rotate a cube or shuffle a deck of cards. For decades, mathematicians have studied these groups using strict algebra, which is like reading the code's instruction manual. But what if you could look at the shape of the code instead?

That's exactly what this paper does. The authors built a giant digital playground containing 131,406 unique maps, called Cayley graphs. Think of these maps as city layouts where every intersection is a move you can make in the group, and the streets show you how to get from one move to another. They generated these maps for every possible group up to a size of 767 (skipping the tricky size of 512 because there were just too many to handle at once).

The Big Discovery: Shapes Tell Stories
The main finding is that these map shapes are surprisingly good at revealing the group's secret identity. Just by looking at the geometry of the map—how far apart the intersections are, how many loops exist, or how "clumped" the streets are—a computer can guess whether the group is "abelian" (where the order of moves doesn't matter, like putting on socks then shoes vs. shoes then socks) or "nilpotent" (a specific type of orderly group).

The authors didn't just guess; they ran a massive experiment. They fed these maps into different types of AI "detectives."

The Old-School Detectives: These used a list of pre-calculated stats (like the average distance between points). They were very good at their job, especially for finding "nilpotent" groups.
The New AI Detectives (Graph Neural Networks): These looked at the raw map without any pre-made stats. One specific type, called GIN, turned out to be a superstar. It learned to spot "nilpotent" groups even better than the old-school detectives, proving that the AI could find the hidden patterns in the map's structure all by itself.

What They Ruled Out (The "Not-So-Simple" Truth)
The paper explicitly argues against a few common hopes. First, they found that you can't just look at one simple feature (like the "square clustering" of a map) to instantly tell if a group is "abelian." It's not that simple; the maps are too complex for a single trick. Second, they showed that while some AI models (like a basic "MLP" that ignores the map's connections) could guess some things, they often failed miserably on harder tasks, defaulting to random guesses. This proves that you need to understand the map's connections to get the answer right; you can't just treat the map as a random list of numbers.

How Sure Are They?
The authors are very confident about the data they collected. They didn't just simulate a few examples; they built a complete census of 131,406 groups. They verified their counts against known mathematical lists (called OEIS sequences) and even added four new sequences to the official math encyclopedia for groups they counted that no one had listed before.

However, when it comes to the patterns they found in the maps, they are careful. They say these patterns "suggest" new mathematical ideas, but they haven't been mathematically proven yet. For example, they noticed that for "perfect" groups (the most chaotic kind), the maps never have certain square-shaped loops. They suspect this is always true, but they call it a "conjecture" (a strong guess) rather than a law. Similarly, they found a weirdly perfect relationship between the "disorder" of a map and its size, but they frame it as an observation that needs more proof.

The Takeaway
This paper is like discovering that every secret society has a unique fingerprint made of streets and intersections. The authors built a massive database of these fingerprints and showed that modern AI can read them to identify the society's rules. While they haven't solved every mystery in the library, they've proven that looking at the shape of the math is a powerful new way to understand symmetry, and they've left the door wide open for future explorers to prove the new theories they've spotted.

Technical Summary: Learning the Graphical Nature of Symmetries

Problem Statement

Finite groups are rigid algebraic structures whose properties are often difficult to visualize or compare directly. While Cayley graphs provide a geometric representation of these groups by converting algebraic multiplication into graph connectivity, the extent to which specific algebraic properties (e.g., nilpotency, simplicity, solvability) are encoded in the observable network statistics of these graphs remains an open question. Furthermore, it is unclear whether modern graph machine learning models, specifically Graph Neural Networks (GNNs), can recover structural group information directly from Cayley graph data without relying on hand-crafted algebraic or graph-theoretic features. This study addresses the interface of computational group theory, network analysis, and graph machine learning by asking: To what extent do readily computable network features of a Cayley graph encode enough information to predict the structural properties of the underlying finite group?

Methodology

Dataset Construction

The authors constructed a comprehensive census of 131,406 Cayley graphs derived from the GAP Small Groups library. The dataset covers all finite groups of order up to 767, excluding groups of order 512 (due to computational constraints regarding the sheer number of such groups, ~10.5 million).

Generation: Using GAP and the networkx library, Cayley graphs were generated for each group using the GeneratorsOfGroup function. The resulting graphs are directed, regular, and vertex-transitive.
Labels: The dataset includes exact algebraic labels for seven binary group properties: Abelian, Nilpotent, Simple, Perfect, Solvable, Monolithic, and Cyclic.
Features:
- Algebraic: Minimal number of generators.
- Graph Statistics: Density, diameter, girth, average and square clustering coefficients, topological indices (Wiener, Gutman, Schultz), cycle basis statistics (lengths, counts), and spectral descriptors of the normalized Laplacian (Fiedler eigenvalue, eigenvalue spread, gap indices).

Machine Learning Framework

The study evaluates four families of models to predict the seven algebraic properties from the Cayley graph data:

Classical Baselines: Logistic Regression, Random Forest, and XGBoost. These models operate on precomputed, hand-crafted graph statistics (the vector of network observables).
MLP Baseline: A feed-forward Multi-Layer Perceptron trained on the raw edge list (zero-padded adjacency information) to measure signal recoverable without graph-structured inductive bias.
Graph Neural Networks (GNNs):
- GCN (Graph Convolutional Network): Uses degree-normalized mean aggregation (low-pass filter).
- GIN (Graph Isomorphism Network): Uses sum aggregation followed by an MLP, proven to be as expressive as the Weisfeiler-Leman test.
- Input Strategy: Since Cayley graphs lack intrinsic node features, the models were initialized with a trivial signal (constant vector or Laplacian eigenvectors) and allowed to diffuse across the topology. Global mean pooling was used for graph-level classification.

Analysis Strategy

The authors performed extensive correlation analysis between graph statistics and group properties to identify empirical regularities and formulate conjectures. They also conducted comparative experiments on the full dataset and a restricted subset of groups of order 256 to isolate order-dependent signals from intrinsic structural features.

Key Contributions

1. A Large-Scale Benchmark Dataset

The paper provides the first exhaustive dataset of Cayley graphs for groups up to order 767, linking exact algebraic labels with a broad collection of network, cycle, distance, and spectral statistics. This serves as a controlled benchmark for studying how algebraic phenomena manifest in graph observables.

2. New Enumerative Results (OEIS Sequences)

Beyond machine learning, the census yields new mathematical contributions:

Recovery of known OEIS sequences for standard group classes (cyclic, abelian, nilpotent, simple, perfect, solvable).
New Sequences: The authors contributed new sequences to the OEIS for:
- The number of monolithic groups (Sequence A395682).
- The number of groups generated by at most three, four, and five elements (Sequences A396721, A394617, A394618).

3. Empirical Regularities and Conjectures

Network analysis revealed several non-trivial correlations and formulated testable conjectures:

Perfect Groups: All observed perfect groups had a directed square clustering coefficient of zero, leading to the conjecture that perfect groups (maximally non-abelian) cannot form directed squares under appropriate generator restrictions.
Diameter and Generators: A strong relationship was observed where the graph diameter is bounded by the ratio of group order to the minimal number of generators ( $n/g_{min}$ ), with specific exceptions for groups of the form $(\mathbb{Z}/2\mathbb{Z})^k$ .
Disorder and Diameter: An "almost perfect" linear relationship was found between the average graph disorder and the product of group order and graph diameter ( $n \cdot D \approx A$ ).
Spectral Conjecture (Nilpotent Groups): The distribution of the "first-large-gap index" in the Laplacian spectrum of nilpotent groups is trimodal. The authors conjecture that these gaps correspond to the indices of quotients in the upper central series of the group ( $|G/Z_j(G)|$ ).

4. Machine Learning Performance

Hand-Crafted Features: Classical ensemble methods (Random Forest, XGBoost) trained on precomputed graph statistics performed strongly, confirming that these invariants encode significant algebraic information.
GNNs vs. Tabular Models: GIN demonstrated superior performance on the nilpotent classification task, outperforming tabular models even though it did not have access to expensive precomputed features like the minimal cycle basis. This suggests GNNs can recover structural signals relevant to nilpotency directly from the graph topology.
Architecture Sensitivity: GCN performed poorly on several tasks (e.g., abelian, monolithic), likely due to over-smoothing on regular graphs, whereas GIN's sum aggregation preserved necessary structural distinctions.
Fixed-Order Challenge: In the restricted order-256 experiment (focusing on monolithic groups), GNNs remained competitive with tabular methods, though the extreme class imbalance made definitive conclusions difficult.

Significance and Claims

The paper claims that Cayley graphs provide a "productive bridge" between finite group theory, network science, and graph machine learning. Its primary significance lies in demonstrating that:

Substantial Signal Exists: Even for generator-dependent constructions, substantial and interpretable statistical signals survive in Cayley graphs that allow for the prediction of deep algebraic properties.
GNNs are Viable: Graph neural networks, particularly GIN, can learn to predict group-theoretic properties directly from raw graph data, offering a pathway to avoid expensive feature engineering (such as computing minimal cycle bases) when such descriptors are unknown or computationally prohibitive.
Data-Driven Discovery: The study validates a methodology where large-scale computational censuses can generate new mathematical conjectures (e.g., regarding eigengaps in nilpotent groups) and new enumerative sequences, complementing traditional theoretical approaches.

The authors maintain a modest stance, noting that while the results are promising, the conjectures remain open to proof or counterexample, and the machine learning results are heavily influenced by class imbalance and the specific choice of generating sets. The work is presented as a foundational step toward a broader program of data-driven discovery in algebra.