Graph neural networks pass information along edges, so when two parts of a graph are joined by only a few edges (a "bottleneck"), signals from far away get crushed together and lost. This failure is called over-squashing. One effective fix is to add a sparse extra graph with strong connectivity, an expander (a graph with no bottlenecks anywhere), and let messages alternate between the input graph and the expander. Cayley Graph Propagation (CGP) does this with the full Cayley graph of the matrix group $SL(2,\mathbb{Z}_n)$. A Cayley graph is the graph whose nodes are group elements and whose edges multiply by a fixed set of generators. CGP shows that cutting such a graph down to the input size destroys its expansion. It therefore keeps the whole graph and pads with virtual nodes. The cost is that input nodes are placed on the expander arbitrarily, and the authors name structure-aware placement as an open problem.
We propose to replace the single expander with a tower of coverings: a chain of Cayley graphs $SL(2,\mathbb{Z}_{3^k}) \to SL(2,\mathbb{Z}_{3^{k-1}}) \to \dots \to SL(2,\mathbb{Z}_3)$. Each graph in the chain folds onto the next, and the group that says which fine nodes land on the same coarse node is a finite 3-group. Clusters of the input graph are placed on the nodes of the coarse Cayley graph, and nodes inside a cluster are placed on the fibre above that coarse node. Graph locality then matches group structure at every scale, and no level of the tower is ever cut down. The theory of $p$-group coverings, whose clean statement is the hyperfocal subgroup theorem, tells us which covering layers exist. A simple spectral fact guarantees that expansion survives at every level. A regularity condition borrowed from shape digitization keeps clusters from being thin slivers that would bring bottlenecks back.
Core Claim
A structure-aware placement onto a covering tower of complete Cayley expanders will beat CGP's arbitrary placement on long-range benchmarks, with no loss of CGP's expansion guarantee. The guarantee comes from how quotients inherit eigenvalues. If $\pi: X \to Y$ is a covering of finite regular graphs whose fibres are orbits of a group of symmetries, every eigenvector of $Y$ lifts to one on $X$. So
$$\operatorname{spec}(A_Y) \subseteq \operatorname{spec}(A_X), \qquad \lambda_2(Y) \le \lambda_2(X),$$
where $A$ is the adjacency matrix and $\lambda_2$ is the second-largest eigenvalue. The spectral gap $d-\lambda_2$ of each coarser level is therefore at least that of the finest level. Congruence quotients of $SL(2,\mathbb{Z})$ with fixed generators form a uniform expander family; this is the property-$(\tau)$ regime in Expanders, rank and graphs of groups. As a result, every level of the tower has a Cheeger constant bounded away from zero. Lackenby's trichotomy says that, in the absence of this property, deep covers must either split as amalgamated products or HNN extensions or have vanishing rank gradient. This is why we build towers only from groups with that property.
The new element is not the expander. It is the covering-compatible placement, together with an explicit regularity constraint on clusters.
Role of the Two Directions
Hyperfocal direction: which covering layers exist. Extensions of p-local finite groups shows that covering spaces of a $p$-local classifying space correspond to subgroups. It also proves $\pi_1(|\mathcal{L}|)\cong S/O^p(S)$: the $p$-group quotients available are controlled by the hyperfocal subgroup $O^p(S)$, which is computable from local fusion data. We use this as the rule for enumerating candidate towers. A layer whose covering group is a $p$-group exists exactly when the relevant $p$-power quotient is nontrivial. For the congruence tower, the kernel of $SL(2,\mathbb{Z}_{9})\to SL(2,\mathbb{Z}_3)$ has order $27$, and later kernels are elementary abelian of order $27$. The node counts are therefore $24$, $648$, $17{,}496$, which match molecules, Peptides, and superpixel graphs (about 480 nodes, per Long Range Graph Benchmark) at useful scales.
We state plainly what this direction does not contribute. The empirical claims do not depend on exotic fusion systems. The theory supplies design vocabulary and an enumeration rule; it is not a new theorem.
Regularity direction: a constraint on clusters. Shape Preserving Digitization of Binary Images After Blurring proves that sampling preserves a shape's topology when the shape is $r$-regular with $r > r' + p$. Informally, a ball of radius $r$ rolls freely inside and outside its boundary. The analogous risk in our setting is a partition cell that is a long thin path. Placing such a cell on a fibre, which is a small ball-like set in the expander, would distort distances badly.
We impose a graph analogue of $r$-regularity. Every cluster must contain a graph-metric ball of radius at least $r$, where $r$ is compared against the cluster diameter. We treat violation as a partitioning penalty, not a hard proof condition. The Mumford–Shah cone-property work in Existence of minimizers of the Mumford-Shah functional plays the same role in the continuum: it forbids cusp-like jump sets so that compactness holds. It motivates the constraint but supplies no technique we reuse.
Research Program
Step 1: tower library. We build the congruence towers for $p=3$ and $p=5$. The $p=5$ tower is $120 \to 15{,}000$ nodes. For each level we verify $\lambda_2$ and Cheeger estimates numerically, as a sanity check on the eigenvalue-inclusion argument.
Step 2: placement algorithm. We partition each input graph into $|G/N|$ balanced clusters using spectral partitioning with the inradius penalty. We then solve a quadratic assignment of clusters to coarse Cayley nodes that places clusters joined by input edges at nearby coarse nodes. Next we assign nodes within each cluster to the fibre by the same procedure, recursively. Unused fibre slots become virtual nodes, as in CGP. Everything is precomputed once per graph.
Step 3: architecture. Local message-passing layers (GIN or GCN) alternate with Cayley layers. The Cayley layers can be taken at a fixed level or cycled coarse-to-fine.
Step 4: analysis. We measure the sensitivity of a node's output to distant inputs, which is the Jacobian quantity that Understanding over-squashing and bottlenecks on graphs via curvature ties to curvature. We also measure distortion between input-graph distance and backbone distance, and effective resistance.
Baselines
Naive reference. The plain local message-passing network (GIN/GCN) with no backbone and no rewiring. On Peptides-func, Long Range Graph Benchmark reports a test average precision of 0.5930 for GCN.
Strongest direct competitor: CGP (Cayley Graph Propagation). It uses the same group family and the same virtual-node trick, so it isolates our placement idea exactly. It reports a test ROC-AUC of 0.7899 on ogbg-molhiv with a GIN backbone, versus 0.7537 for the truncated-expander method EGP. The file gives no exact scalar for CGP on Peptides (no reported result found on Lacuna beyond "outperforms SDRF and FoSR"), so we will rerun it.
Fairness conditions. All methods share the same backbone networks, hidden widths, layer counts, and hyperparameter search budget. Evaluation uses at least five seeds. CGP is run on the finest tower level, so both methods see the same number of Cayley nodes.
Rewiring and attention baselines. We include SDRF, which reports 70.35% versus 61.19% for the baseline on Texas, and AFR-k from Mitigating Over-smoothing and Over-squashing, which reports about 4% improvement on Peptides-func. These are the strongest methods that do not use a fixed graph backbone. We also include SAN at 0.6439 average precision on Peptides-func, as the dense-attention ceiling.
Ablations. Two ablations isolate our ingredients. The first uses the same tower with random placement, which tests whether placement matters. The second uses our placement without the inradius penalty, which tests whether the regularity constraint matters.
What counts as success. We count it as beating CGP if our method exceeds CGP's rerun score by more than the seed standard deviation on molhiv and on at least two long-range benchmark tasks.
Why not just…?
Why not just use CGP with a smarter node ordering on a single expander? A single Cayley graph has no coset structure aligned with clusters. Any ordering places a cluster on a set of nodes with no guaranteed compactness, so locality is lost. The random-versus-structured placement ablation on a single level directly measures how much ordering alone buys. If a single-level sorted placement matches the tower, we will report the tower as unnecessary.
Why not just coarsen the graph and attach a separate expander at each scale? This is the most serious threat. Independent expanders per level give multi-scale routing but no guaranteed consistency between scales. A coarse neighbour is not the image of a fine neighbour, and each junction between scales is a potential bottleneck. We run exactly this baseline: independent CGP graphs of matching sizes, connected cluster-to-node. If it ties with our method, the covering structure, and with it the group-theoretic content, adds nothing, and we will say so.
Why not just rewire with curvature flow? SDRF and AFR-k fix bottlenecks locally and give no global expansion guarantee. BORF timed out after an hour on Tolokers according to Mitigating Over-smoothing and Over-squashing. They are included as full baselines, and the comparison of the Jacobian-sensitivity measure will show whether local rewiring reaches the same distant nodes.
Why not just use a graph transformer? Attention across all node pairs costs memory quadratic in the number of nodes, and fully adjacent variants run out of memory on large graphs per CGP. SAN is our accuracy ceiling. The claim is to approach it at sparse cost, not necessarily to beat it.
Proposed Experiments
Benchmarks and tower levels. We evaluate on ogbg-molhiv (tower levels 24/648), the Long Range Graph Benchmark tasks Peptides-func, Peptides-struct, and PascalVOC-SP (648 and 17,496), and the heterophilous datasets Texas and Cornell. We report accuracy, average precision, mean absolute error, or ROC-AUC as appropriate, plus preprocessing and training time.
Decisive check 1. Structure-aware placement must beat random placement on the same tower on the long-range tasks. This is where locality should matter most, since molhiv graphs are small.
Decisive check 2. The covering tower must beat independent per-scale expanders.
Decisive check 3. Measured distance distortion and distant-node Jacobian sensitivity must track the accuracy gains. If accuracy improves while distortion does not change, the mechanism is not what we claim.
Negative result we would report. If gains vanish once cluster counts are matched, the contribution reduces to a better padding scheme for CGP.
References
- Cayley Graph Propagation
- Expanders, rank and graphs of groups
- Extensions of 𝑝-local finite groups
- Long Range Graph Benchmark
- Shape Preserving Digitization of Binary Images After Blurring
- Existence of minimizers of the Mumford-Shah functional with singular operators and unbounded data
- Understanding over-squashing and bottlenecks on graphs via curvature
- Mitigating Over-smoothing and Over-squashing using Augmentations of Forman-Ricci Curvature