Some graphs look identical from every vertex. Even so, their edges can split into several genuinely different kinds. Tri-Cayley graphs produce exactly this situation, and they produce it on demand. A tri-Cayley graph is built from a finite group $H$: its vertices are three copies of $H$, and a few subsets of $H$ say which vertices to join. Recent algebraic work constructs 4-valent families of these graphs (every vertex has four neighbours) and proves that every vertex is equivalent to every other under the graph's symmetries. The same work proves that the edges are not all equivalent, because some edges lie on triangles and others do not.
That combination is the hardest case for standard graph neural networks. In a 4-regular graph where all vertices are equivalent, a message-passing network gives every vertex the same embedding. Any edge prediction it builds from vertex embeddings is therefore constant. This proposal turns the algebra into an instrument. We will enumerate tri-Cayley graphs over small cyclic and non-abelian groups and label each one exactly by computing its full automorphism group. We then measure which local signals actually separate the true edge classes: triangle counts, longer cycle counts, Weisfeiler–Leman refinement, subgraph networks, and an interpretable concept model. The scientific target is a question the classification papers leave open. We want to know when edge symmetry breaking in a vertex-transitive tri-Cayley graph is detectable from local structure, how much local structure is needed, and whether a learned model can recover that rule from small groups and apply it to large ones.
Core Claim
For vertex-transitive tri-Cayley graphs, define the certificate radius of a graph as the smallest cycle length $k$ such that rooted cycle counts of length at most $k$ separate all edge orbits. An edge orbit is a set of edges that the graph's automorphisms can map onto each other. If even the 2-dimensional Weisfeiler–Leman coloring of vertex pairs fails to separate them, the radius is unbounded.
We claim three things. First, this radius is computable exactly over a large census. Second, it stays small for the cyclic 0-type and 2-type families studied so far, where triangles suffice. Third, it is not uniformly small across the tri-Cayley parameter space once $H$ is non-abelian or the internal valencies differ across the three orbits. If the third claim holds, the census becomes a benchmark with exact ground truth for a capability that symmetry-aware learning papers assert but rarely test. That capability is telling apart edges that look locally alike but are not equivalent. If the claim fails, and triangles always suffice, that is itself a conjecture worth proving. It would also tell the learning community that these graphs test triangle counting and nothing more.
Background and How This Differs
The mathematical side supplies the objects and the mechanism. Ye and Zhang construct two classes of 4-valent tri-Cayley graphs over cyclic groups. One class has no edges inside the three vertex copies (called 0-type). The other has a cycle inside each copy (called 2-type). They prove both classes vertex-transitive but neither edge- nor arc-transitive, using exactly the triangle argument. Arc-transitive means every directed edge can be mapped to every other. Ye extends this to $H=\mathbb{Z}_{pq}$, with three explicit families and their full automorphism groups. Work on cubic bi-Cayley graphs over semidihedral groups shows how the same methods handle non-abelian groups in the two-orbit case.
These papers motivate the proposal: they establish the phenomenon. They are also entirely pen-and-paper. They stop at cyclic groups, and they explicitly list classification over non-abelian groups as future work. We do not attempt a classification proof. We build the computational census those proofs lack and ask what it reveals.
The learning side supplies the methods and the claims under test. Autobahn applies convolutions that respect the internal symmetry of hand-chosen subgraphs. Its ZINC 10k mean absolute error of 0.106, against 0.367 for a plain GCN, shows that injecting local cycle structure matters on molecules. Graph Automorphism Group Equivariant Neural Networks characterizes linear layers equivariant to a graph's exact automorphism group. That paper is purely theoretical and evaluates on no graph family. Interpretable Graph Networks uses a discrete concept bottleneck (a layer that forces node embeddings into a small vocabulary of recognisable patterns) to rediscover the forbidden sublattices behind modularity and distributivity. On finite lattices it reports AUC-ROC "often >99%" and generalizes from 8 to 50 nodes.
We reuse the iGNN idea of a readable concept layer, but move it from the vertices of lattices to the edges of group-built graphs, where the target is an orbit partition rather than a forbidden pattern. We use Autobahn and subgraph networks as competitors, not as components. The census also gives the first concrete testbed where the exact symmetry group is known, which is what equivariance theory needs before it can be evaluated.
Cayley-graph routing work, namely Expander Graph Propagation and Cayley Graph Propagation, uses Cayley graphs only as communication scaffolds. It constrains this proposal rather than supplying anything to it, for reasons given below.
Research Program
Census construction. For every group $H$ of order up to about 60, we enumerate 4-valent parameter sets $\mathrm{TCay}(H; L_0,L_1,L_2; S_0,S_1,S_2)$ up to the obvious relabelings. The groups covered are cyclic, abelian non-cyclic, dihedral, and the non-abelian groups $\mathbb{Z}_p\rtimes\mathbb{Z}_q$. The parameter sets include 0-type, 2-type, and mixed types in which the internal valency differs across orbits. We remove duplicate graphs by canonical labeling. With an exact graph-automorphism package we compute the full automorphism group, vertex orbits, edge orbits, and arc orbits. We keep the vertex-transitive graphs, which are the only ones where 1-WL is fully blind.
The first sanity check is mechanical. The census must reproduce Ye's statements about $\Phi_1,\Phi_2,\Phi_3$, including the stated automorphism group structures, and Ye–Zhang's $X_1, X_2$. Any disagreement is reported, not smoothed over.
The radius measurement. For each graph we compute rooted cycle profiles on edges for lengths 3 through 8. We also compute the stable 2-WL coloring of vertex pairs, and the 3-WL coloring for graphs small enough. Each produces a partition of the edges, which we compare to the true edge-orbit partition. These signals can only merge distinct orbits, never split a single orbit, so the comparison asks how much they merge. This yields the certificate radius for every graph. It also flags the subset where 2-WL itself merges distinct orbits. On those graphs, any model bounded by 2-WL must fail, whatever its training.
Learning tasks. Task A is edge-orbit recovery: given the graph, predict for each pair of edges whether they share an orbit. We score it by adjusted Rand index (ARI, a measure of agreement between two partitions, 1 for perfect agreement) against the true partition. Task B is graph-level: predict edge-transitivity and arc-transitivity.
Both tasks have two transfer splits. In the size split, models train on groups of order at most 30 and are tested at orders 60 to 300, where exact labels remain cheap to compute. In the group split, models train on cyclic and abelian groups and are tested on dihedral and $\mathbb{Z}_p\rtimes\mathbb{Z}_q$ groups.
Proposed model. The model is an edge-level concept bottleneck. Each edge starts with its rooted cycle profile up to length $k$, together with a tag saying whether it joins vertices in the same copy of $H$ or in different copies. The three copies are known from the construction. Message passing then runs over the line graph, in which edges become nodes and are linked when they share an endpoint. Next a discrete concept layer of the iGNN kind assigns each edge to one of a small set of concepts. Finally, a transparent head turns those concepts into the orbit partition and the transitivity label.
The point is not raw accuracy, which an exact oracle already provides. The point is a readable rule that holds at sizes the model never saw. An example would be "edges in a 4-cycle that crosses all three copies form a separate orbit." Every rule the model extracts is checked by the oracle on held-out groups. Rules that survive become explicit conjectures about which connection sets break edge-transitivity.
Baselines
The naive reference is a 1-WL-bounded message-passing network (GIN) given only adjacency. On vertex-transitive 4-regular inputs every vertex embedding is identical, so it must predict a single edge class. Its ARI is therefore 0 whenever there is more than one orbit. We run it anyway to confirm the pipeline. We also run GIN with the copy tag added. This shows how much the construction metadata alone carries, and it fixes the floor any structural method must clear.
The strongest simple competitor is a non-learned one: edge triangle counts, then rooted cycle profiles up to length $k$, fed to logistic regression or a depth-limited decision tree. This is exactly the certificate the published proofs use. On any graph whose radius is 3 it is a perfect classifier, so it is the bar the learned model must clear on the hard subset. We also report the stable 2-WL edge partition as an oracle upper bound for every 2-WL-bounded learner.
The strongest learned competitors are an Autobahn-style network with cycle templates of lengths 3 to 6 and a nested subgraph network that applies message passing within each edge's neighbourhood. These are the closest existing methods that see local cycle structure. For orbit recovery on these graph families: no reported result found on Lacuna. The nearest reported figures are Autobahn's 0.106 ZINC 10k mean absolute error, on molecules, and iGNN's AUC-ROC often above 99%, on lattices. Neither transfers here, so every number will be produced inside this study.
All learned models share the same splits, the same feature budget (cycle lengths up to $k$), a matched parameter count, and the same hyperparameter search of 50 trials per model.
Beating the competition means three things on the hard subset, where triangle profiles merge distinct orbits but 2-WL does not:
- ARI at least 0.1 above the best cycle-profile decision tree using the same $k$, on the size-extrapolation split.
- Extracted rules that the oracle confirms on at least 95% of held-out graphs.
- Performance within 0.05 ARI of the 2-WL oracle.
Two ablations isolate the proposal's ingredients. Removing the copy tag tests whether knowing the three-orbit structure of $H$ matters. Replacing the discrete concept layer with a continuous one tests whether readability costs accuracy or buys extrapolation.
Why not just…?
Why not just run nauty or GAP and skip learning? For labeling, we do exactly that. Exact automorphism computation is the oracle throughout, and it handles graphs with thousands of vertices easily. We do not claim learned models are faster or more reliable at this. The scaling advantage reported by CayleyPy RL, where GAP stalled near $n\approx20$ for pathfinding in $S_n$, concerns word problems in enormous groups, not automorphism computation on modest graphs, so it does not apply. What an oracle cannot give is a uniform reason across infinitely many groups. The learning arm is justified only if it yields rules that the oracle then confirms at larger orders. If extracted rules fail that check, the learning claim fails, and the census plus radius measurements stand as the contribution.
Why not just count triangles, as the proofs do? This is the real threat. If every vertex-transitive graph in the census has radius 3, triangle profiles solve Task A perfectly, and no network is needed. The radius measurement settles this before any training. We commit to reporting the fraction of graphs where triangle counts merge distinct orbits. If that fraction is negligible, we drop the learning comparison. We would then reframe the result as an empirical conjecture that triangle counts certify edge-orbit structure in 4-valent vertex-transitive tri-Cayley graphs over all small groups, and as a warning that such graphs are weak expressivity benchmarks.
Why not just use random 4-regular graphs or existing expressivity benchmarks? Random regular graphs almost never have nontrivial symmetry, so they offer no edge orbits to recover. Existing benchmarks rarely come with exact symmetry groups. Tri-Cayley parameters let us choose the group, the orbit type, and the size independently, which is what makes the transfer splits clean.
Why not instead build tri-Cayley expanders for long-range message passing, extending CGP? The size argument is tempting: tri-Cayley graphs over $\mathbb{Z}_n$ exist at every multiple of three. However, graphs built from cyclic groups have spectral gaps that shrink with $n$, so they cannot match the $\mathrm{SL}(2,\mathbb{Z}_n)$ expanders that Cayley Graph Propagation relies on. Random regular overlays would fill the size gaps more cheaply. We judged that direction likely to lose to a simpler alternative and did not pursue it.
Decisive Checks
The program hinges on four results, taken in order. First, the census must reproduce the published theorems on $\Phi_1,\Phi_2,\Phi_3,X_1,X_2$. Second, the distribution of certificate radii must show whether triangle-tie graphs exist, and in which groups and types. Third, on that hard subset, the concept model must beat the cycle-profile decision tree under size and group extrapolation. Fourth, at least one extracted rule about connection sets must survive oracle verification at group orders ten times larger than training, and be stated precisely enough for a proof attempt. Each check can fail independently, and each failure leaves a usable, honestly scoped result.
References
- The Construction of two classes of 4-valent triCayley Graphs over Cyclic Group
- A Classification of 4-Degree Tri-Cayley Graphs Over a Group of Order 𝑝q
- A classification of connected cubic vertex-transitive bi-Cayley graphs over semidihedral group
- Autobahn: Automorphism-based Graph Neural Nets
- Graph Automorphism Group Equivariant Neural Networks
- Interpretable Graph Networks Formulate Universal Algebra Conjectures
- Expander Graph Propagation
- Cayley Graph Propagation
- CayleyPy RL: Pathfinding and Reinforcement Learning on Cayley Graphs