Schreier-Coset Graph Rewiring

# Schreier Coset Graph Rewiring
Source: [https://arxiv.org/html/2607.27479](https://arxiv.org/html/2607.27479)
Randy Martinez11footnotemark:1Lizhen Linlizhen01@umd\.edu

###### Abstract

The information flow in the graph neural networks \(GNNs\) is fundamentally constrained byover\-squashing, where structural bottlenecks impede long range information propagation\. Graph\-rewiring methods, which modify graph topology, have been extensively used to alleviate this\. However, existing approaches often introduce prohibitive structural and computational bottlenecks, fail to preserve the critical properties of original graphs, and increase the edge counts massively\. We introduce a novel methodSchreier\-Coset Graph Rewiring, a group\-theoretic rewiring method that augments the input graph with a Schreier\-Coset graph derived from a special linear group\. Our method provides theoretical guarantees, a graph that exhibits spectral gap and a bounded effective resistance, creating a low\-resistance bypass for long\-range communication\. Empirical evaluations demonstrate that SCGR reduces effective resistance by55–40%40\\%across various learning tasks, effectively mitigating connectivity bottlenecks while maintaining competitive accuracy\.

## 1Introduction and Related Works

Graphs are network structures that represent relationships by connecting entities \(nodes\) with the other entities using connection links \(edges\)Harary \([1969](https://arxiv.org/html/2607.27479#bib.bib1)\); Diestel \([2012](https://arxiv.org/html/2607.27479#bib.bib2)\); Shumanet al\.\([2013](https://arxiv.org/html/2607.27479#bib.bib3)\); Hamiltonet al\.\([2017a](https://arxiv.org/html/2607.27479#bib.bib4)\)\. The ability of graphs to capture relational and structural information makes them invaluable across diverse fields such as biology, topology, recommendation systems and connected structural informationBattagliaet al\.\([2018](https://arxiv.org/html/2607.27479#bib.bib5)\); Sanchez\-Gonzalezet al\.\([2018](https://arxiv.org/html/2607.27479#bib.bib6)\); Gilmeret al\.\([2017](https://arxiv.org/html/2607.27479#bib.bib7)\); Berget al\.\([2017](https://arxiv.org/html/2607.27479#bib.bib9)\); Kohet al\.\([2024](https://arxiv.org/html/2607.27479#bib.bib8)\)\.

Graph Neural Networks \(GNNs\) are a specialized class of neural networks developed to process graph structural data\. GNNs typically operate in a message passing paradigmHeet al\.\([2023](https://arxiv.org/html/2607.27479#bib.bib13)\), where nodes iteratively exchange and aggregate information from their neighbors to update the node representationsJianget al\.\([2019](https://arxiv.org/html/2607.27479#bib.bib10)\); Kipf \([2017](https://arxiv.org/html/2607.27479#bib.bib11)\); Veličkovićet al\.\([2017](https://arxiv.org/html/2607.27479#bib.bib12)\)\. To capture long\-range information or interactions within graphs, deep GNN architectures are often necessary\. However, increasing the number of layers often introduces structural and computational bottlenecks\. In particular, this results in large amount of information from extensive neighborhoods being compressed into fixed size embeddings, known asover\-squashingAlon and Yahav \([2021](https://arxiv.org/html/2607.27479#bib.bib14)\); Arnaiz\-Rodriguez and Errica \([2025](https://arxiv.org/html/2607.27479#bib.bib24)\)\. Over\-squashing curbs the ability of GNNs to capture long range dependencies, thus degrading performance tasks that need global context\.

Various methods have been employed to address over\-squashing in GNNs\. InFeature Augmentation, node/edge attributes are enriched with global signals\.Eliasofet al\.\([2023](https://arxiv.org/html/2607.27479#bib.bib35)\)concatenate top\-kkLaplacian eigenvectors to each node, thus long\-range information does not propagate hop by hop\. However, eigen\-decomposition, which costsO​\(n3\)O\(n^\{3\}\)andO​\(n​k\)O\(nk\)memory, suffers from batch inefficiency\.Graph Rewiringmodifies the input \(original\) graph by*a\) adding nodes*or*b\) reconfiguring the edges*to generate an output graph that enhances connectivity between nodes\. For instance,Deacet al\.\([2022](https://arxiv.org/html/2607.27479#bib.bib15)\)construct expander graphs\.Wilsonet al\.\([2024](https://arxiv.org/html/2607.27479#bib.bib16)\)use Cayley graphs to aid propagation\. Some other work modify topology using properties such as curvatureFesser and Weber \([2024](https://arxiv.org/html/2607.27479#bib.bib17)\), spectral expansionKarhadkaret al\.\([2023](https://arxiv.org/html/2607.27479#bib.bib18)\)and effective resistanceBlacket al\.\([2023](https://arxiv.org/html/2607.27479#bib.bib19)\)to optimize information flow\.

The existing graph rewiring techniques have two limitations:a\) over\-alter the edges of input graphandb\) introduce newer edges\. Expander graph rewiring methods introduce entirely new nodes sets, diverging significantly from the structure of input graphrampášek2023recipegeneralpowerfulscalable\. Graph transformers rely on FCNNs \(fully connected neural networks\) and have quadratic\- computation scaling\. The Delaunay graphs\(Attaliet al\.,[2024](https://arxiv.org/html/2607.27479#bib.bib20)\)provide benefits such as reduced graph diameter and lower effective resistance\. However, it constructs graphs solely based on node features, completely disregarding the original graph topology\.

![Refer to caption](https://arxiv.org/html/2607.27479v1/Figures/SCGR.png)Figure 1:Illustrates the Schreier–coset graph rewiring framework, original graph locality is preserved,dd\-regular graphΓ\\Gammaprovides constant\-degree shortcuts with bounded effective resistance, align nodes via Fiedler Ranking \(OSQrepresentsover\-squashededge link\)Preserving the graph locality is imperative during rewiring, since many learning tasks, such as clustering and semi\-supervised learning on graphs, rely on spectral properties of input graphs to ensure accurate results\. These methods often introduce many additional edges to enhance connectivity, which both increases computational cost of learning on the rewired output graphArnaiz\-Rodriguez and Errica \([2025](https://arxiv.org/html/2607.27479#bib.bib24)\)and the risk of over\-smoothingLiet al\.\([2018](https://arxiv.org/html/2607.27479#bib.bib21)\); Lianget al\.\([2023a](https://arxiv.org/html/2607.27479#bib.bib22),[b](https://arxiv.org/html/2607.27479#bib.bib23)\)\. To address over\-squashing, we proposeSchreier\-Coset Graph Rewiring \(SCGR\)\(referFigure[1](https://arxiv.org/html/2607.27479#S1.F1)for a schematic flow of our method\), a group theoretic approach based on the*Schreier\-Coset Graph*constructed from the cosets of the special linear groupS​L​\(2,ℤn\)SL\(2,\\mathbb\{Z\}\_\{n\}\)\.

##### Contributions\.

Our main contributions are summarized as follows:

- •Schreier\-Coset \(SCGR\) formalization :We define the novel construction of the Schreier\-Coset graphs and their application in rewiring augmentations in GNNs\. The vertices corresponding to cosets of theS​L​\(2,ℤn\)SL\(2,\\mathbb\{Z\}\_\{n\}\)modulo an upper\-triangle subgroup, with constant generators yielding add\-regular graph\.
- •Theoretical Analysis :We provide strong theoretical guarantees of SCGR by defining and deriving the node\-coset mappings, spectral properties, effective resistance bounds on the augmented graph, and over\-squashing mitigation guarantees\.
- •Empirical Evaluation :We evaluateSCGRon node and graph classification benchmarks, and test accuracy and ER bounds by varying modularity of SBM \(Stochastic Block Model\) graphs\. Our extensive numerical results demonstrate thatSCGRconsistently matches or attains higher scores against rewiring baselines\.

### 1\.1Related Works and limitations

Most approaches, to alleviate over\-squashing, modify the input graph by rewiring it\. Expander graph\-based rewiringDeacet al\.\([2022](https://arxiv.org/html/2607.27479#bib.bib15)\), maintains a small diameter using Cayley graphs, which can have a different node set representation than the input graph\.Blacket al\.\([2023](https://arxiv.org/html/2607.27479#bib.bib19)\)minimizes effective resistance to reduce bottlenecks\.Attaliet al\.\([2024](https://arxiv.org/html/2607.27479#bib.bib20)\)constructs newer graphs based on node features, disregarding the original spectral properties\. FoSRKarhadkaret al\.\([2023](https://arxiv.org/html/2607.27479#bib.bib18)\), improves the first order approximation of the spectral gap by adding edges\. Curvature\-based methods have been implemented to enhance connectivity by adding and removing edges based on geometric principlesToppinget al\.\([2021](https://arxiv.org/html/2607.27479#bib.bib34)\); Nguyenet al\.\([2023](https://arxiv.org/html/2607.27479#bib.bib31)\)\. ProxyGapJamadandiet al\.\([2024](https://arxiv.org/html/2607.27479#bib.bib36)\)based onBraess \([1968](https://arxiv.org/html/2607.27479#bib.bib37)\)modifies the edges\.Qianet al\.\([2024](https://arxiv.org/html/2607.27479#bib.bib38)\)explores probabilistic approaches\. PANDA\(Choiet al\.,[2024](https://arxiv.org/html/2607.27479#bib.bib39)\)proposes alternative message passing mechanisms based on width\.Finkelshteinet al\.\([2024](https://arxiv.org/html/2607.27479#bib.bib40)\)introduces a learned cooperative mechanism in message passing paradigm\. These methods do improve connectivity but aggressively alter the topology, neglecting the original graph spectral properties\.

## 2Schreier\-Coset Rewiring for GNNs

### 2\.1Graph Preliminaries

GraphLetG=\(V,E\)G=\(V,E\)denote an undirected, connected and non\-bipartite graph with node setVVand edge setEEand its adjacency matrixA∈ℝni​n×ni​nA\\in\\mathbb\{R\}^\{n\_\{in\}\\times n\_\{in\}\}with entriesAi​j=1A\_\{ij\}=1if\(i,j\)∈E\(i,j\)\\in Eand0otherwise, where\|V\|=ni​n\|V\|=n\_\{in\}\. The diagonal degree matrixD=diag​\(d1,…,dn\)D=\\mathrm\{diag\}\(d\_\{1\},\\dots,d\_\{n\}\)withDv​v=dvD\_\{vv\}=d\_\{v\}\. The normalized Laplacian isL=D−1/2​\(D−A\)​D−1/2L=D^\{\-1/2\}\(D\-A\)D^\{\-1/2\}\. The eigenvalues ofLLsatisfy0=λ0≤λ1≤⋯≤λni​n−10=\\lambda\_\{0\}\\leq\\lambda\_\{1\}\\leq\\cdots\\leq\\lambda\_\{n\_\{in\}\-1\}\. The eigenvector associated withλ1\\lambda\_\{1\}provides canonical one\-dimensional embeddings of the nodes that reflect graph connectivity\.

Special Linear GroupS​L​\(2,ℤn\)SL\(2,\\mathbb\{Z\}\_\{n\}\)\. Letℤn=ℤ/n​ℤ\\mathbb\{Z\}\_\{n\}=\\mathbb\{Z\}/n\\mathbb\{Z\}denote the ring of integers modulonn, The group𝒢=S​L​\(2,ℤn\)\\mathcal\{G\}=SL\(2,\\mathbb\{Z\}\_\{n\}\)is defined as :

𝒢=S​L​\(2,ℤn\)=\{M∈ℤn2×2∣det\(M\)≡1\(modn\)\},\\mathcal\{G\}=SL\(2,\\mathbb\{Z\}\_\{n\}\)=\\left\\\{M\\in\\mathbb\{Z\}\_\{n\}^\{2\\times 2\}\\mid\\det\(M\)\\equiv 1\\pmod\{n\}\\right\\\},wherenndepends on the input graph size\.

Note thatnnis the not the same as the input graph sizeni​nn\_\{in\}\. We choosennas the smallest prime achieving sufficient Schreier\-Coset coverage\.

Subgroup\.LetH⊂S​L​\(2,ℤn\)H\\subset SL\(2,\\mathbb\{Z\}\_\{n\}\)be a subgroup consisting of diagonal matrices with unit determinant within𝒢\\mathcal\{G\}:

H=\{\(a00d\)∈𝒢∣a​d≡1\(modn\)\}\.H=\\left\\\{\\begin\{pmatrix\}a&0\\\\ 0&d\\end\{pmatrix\}\\in\\mathcal\{G\}\\mid ad\\equiv 1\\pmod\{n\}\\right\\\}\.
Generator\.Let𝕊\\mathbb\{S\}be the generator set:

𝕊=\{\(1±101\),\(10±11\)\}modn\.\\mathbb\{S\}=\\left\\\{\\begin\{pmatrix\}1&\\pm 1\\\\ 0&1\\end\{pmatrix\},\\begin\{pmatrix\}1&0\\\\ \\pm 1&1\\end\{pmatrix\}\\right\\\}\\bmod n\.
Expander Graph\.An expander graph is sparse yet highly connected\. We use pre\-computed expander graphs based on Cayley graphsCay​\(𝒢;𝕊\)\\mathrm\{Cay\}\(\\mathcal\{G\};\\mathbb\{S\}\)derived from special linear groupS​L​\(2,ℤn\)SL\(2,\\mathbb\{Z\}\_\{n\}\)with generating set𝕊\\mathbb\{S\}\. While these graphs have good expansion properties, achieving large node counts is often impractical since\|V​\(Cay​\(𝒢;𝕊\)\)\|=n3​∏prime​p\|n\(1−1p2\)\|V\(\\mathrm\{Cay\}\(\\mathcal\{G\};\\mathbb\{S\}\)\)\|=n^\{3\}\\prod\_\{\\text\{prime\}\\;p\|n\}\\left\(1\-\\frac\{1\}\{p^\{2\}\}\\right\), which creates excessive memory requirements for largenn\. \(nnsatisfies the\|V​\(Cay​\(𝒢;𝕊\)\)\|\|V\(\\mathrm\{Cay\}\(\\mathcal\{G\};\\mathbb\{S\}\)\)\|\)\.

## 3Schreier\-Coset GraphΓ\\Gamma

Schreier\-Coset graphs provide a permutation representation of finitely generated groups on the cosets of a subgroup ofS​L​\(2,ℤn\)SL\(2,\\mathbb\{Z\}\_\{n\}\)\. The SC\-graph plays a crucial role in our method serving as an auxiliary structure that encodes robust expansion and mixing behavior through group\-theoretic symmetries\. Formally, for a group𝒢\\mathcal\{G\}, a subgroupH⊆𝒢H\\subseteq\\mathcal\{G\}, a generating set𝕊⊆𝒢\\mathbb\{S\}\\subseteq\\mathcal\{G\}, the Schreier\-coset graphΓ=\(VΓ,EΓ\)\\Gamma=\(V\_\{\\Gamma\},E\_\{\\Gamma\}\)is defined as:

- •Vertex set:VΓ=\{g​H:g∈𝒢\}V\_\{\\Gamma\}=\\left\\\{gH:g\\in\\mathcal\{G\}\\right\\\}\(collection of left cosets\)\.
- •Edge set:For eachg​H∈VΓgH\\in V\_\{\\Gamma\}and eachs∈𝕊s\\in\\mathbb\{S\}includes as undirected edgeg​H,\(s​g\)​HgH,\(sg\)HinEΓE\_\{\\Gamma\}\.

This yields add\-regular graph withd=\|𝕊\|d=\|\\mathbb\{S\}\|, since each coset has one neighbor for every generator\. In constructing the the Schreier graph, we employ a*canonical construction*\. That is,Γ\\Gammais constructed over the group𝒢=S​L​\(2,ℤn\)\\mathcal\{G\}=SL\(2,\\mathbb\{Z\}\_\{n\}\)with subgroupHHconsisting of diagonal matrices, and use elementary row operations as generators:𝕊=\{\(1±101\),\(10±11\)\}modn\\mathbb\{S\}=\\left\\\{\\begin\{pmatrix\}1&\\pm 1\\\\ 0&1\\end\{pmatrix\},\\begin\{pmatrix\}1&0\\\\ \\pm 1&1\\end\{pmatrix\}\\right\\\}\\mod n\. The resulting Schreier\-coset graph has\|VΓ\|=S​L​\(2,ℤn\)/\|H\|=n​\(n2−1\)/ϕ​\(n\)\|V\_\{\\Gamma\}\|=SL\(2,\\mathbb\{Z\}\_\{n\}\)/\|H\|=n\(n^\{2\}\-1\)/\\phi\(n\)vertices, whereϕ​\(n\)\\phi\(n\)is Euler’s totient function\.

### 3\.1Schreier\-Guided Graph Rewiring

We augment the input graph as seen inAlgorithm[1](https://arxiv.org/html/2607.27479#alg1)\.Gi​n=\(Vi​n,Ei​n\)G\_\{in\}=\(V\_\{in\},E\_\{in\}\)using structure preserving rewiring guided by the Schreier\-Coset graphΓ\\Gamma\. Crucial to this method is a locality\-preserving mapϕ:Vi​n→VΓ\\phi:V\_\{in\}\\to V\_\{\\Gamma\}\.

##### Spectral Mapping Construction\.

LetLi​n,LΓL\_\{in\},L\_\{\\Gamma\}be normalized Laplacian with eigenvectorsψi,ϕi​n\\psi\_\{i\},\\phi\_\{in\}\. We defineΦin​\(v\)=\(ψ2​\(v\),…,ψr\+1​\(v\)\)\\Phi\_\{\\mathrm\{in\}\}\(v\)=\(\\psi\_\{2\}\(v\),\\ldots,\\psi\_\{r\+1\}\(v\)\)andΦΓ​\(x\)=\(φ2​\(x\),…,φr\+1​\(x\)\)∈ℝr\\Phi\_\{\\Gamma\}\(x\)=\(\\varphi\_\{2\}\(x\),\\ldots,\\varphi\_\{r\+1\}\(x\)\)\\in\\mathbb\{R\}^\{r\}

We chooseϕ\\phiby:minϕ​∑\(u,v\)∈EindistΓ​\(ϕ​\(u\),ϕ​\(v\)\)\\min\_\{\\phi\}\\ \\sum\_\{\(u,v\)\\in E\_\{\\mathrm\{in\}\}\}\\mathrm\{dist\}\_\{\\Gamma\}\(\\phi\(u\),\\phi\(v\)\)\\quadSuch that‖ΦΓ​\(ϕ​\(v\)\)−Φin​\(v\)‖2≤ε∀v\.\\quad\\\|\\Phi\_\{\\Gamma\}\(\\phi\(v\)\)\-\\Phi\_\{\\mathrm\{in\}\}\(v\)\\\|\_\{2\}\\leq\\varepsilon\\ \\ \\forall v\.IfVin\|\>\|VΓ\|V\_\{\\mathrm\{in\}\|\>\|V\_\{\\Gamma\}\|\}useq=⌈\|Vin\|/\|VΓ\|⌉q=\\lceil\|V\_\{\\mathrm\{in\}\}\|/\|V\_\{\\Gamma\}\|\\rceildisjoint copies ofΓ\\GammaorΓ×Kq\\Gamma\\times K\_\{q\}and apply the above per copy\.

Algorithm 1Schreier–Coset Transform: Graph Rewiring Method \(Section 3\.1\)Input graph

Gin=\(Vin,Ein\)G\_\{\\mathrm\{in\}\}=\(V\_\{\\mathrm\{in\}\},E\_\{\\mathrm\{in\}\}\)with features

XinX\_\{\\mathrm\{in\}\}; coupling strength

ϵ\>0\\epsilon\>0; selection strategy

SS; Booleanspectral\_map

Augmented graph

GrwdG^\{\\mathrm\{rwd\}\}
=\(Vrwd,Erwd,Xrwd,wrwd\)=\(V^\{\\mathrm\{rwd\}\},E^\{\\mathrm\{rwd\}\},X^\{\\mathrm\{rwd\}\},w^\{\\mathrm\{rwd\}\}\)

n←FindN​\(\|Vin\|,S\)n\\leftarrow\\textsc\{FindN\}\(\|V\_\{\\mathrm\{in\}\}\|,S\)

Γ←SchreierTransform​\(n\)\\Gamma\\leftarrow\\textsc\{SchreierTransform\}\(n\),

Γ=\(VΓ,EΓ\)\\Gamma=\(V\_\{\\Gamma\},E\_\{\\Gamma\}\)
ifspectral\_mapthen

Φin←Gin\\Phi\_\{\\mathrm\{in\}\}\\leftarrow G\_\{\\mathrm\{in\}\}

ΦΓ←Γ\\Phi\_\{\\Gamma\}\\leftarrow\\Gamma

ϕ←FiedlerRanking​\(Vin,VΓ,Φin,ΦΓ\)\\phi\\leftarrow\\textsc\{FiedlerRanking\}\(V\_\{\\mathrm\{in\}\},V\_\{\\Gamma\},\\Phi\_\{\\mathrm\{in\}\},\\Phi\_\{\\Gamma\}\)

else

ϕ​\(u\)←1\+\(\(idx​\(u\)−1\)mod\|VΓ\|\)∀u∈Vin\\phi\(u\)\\leftarrow 1\+\(\(\\mathrm\{idx\}\(u\)\-1\)\\bmod\|V\_\{\\Gamma\}\|\)\\quad\\forall u\\in V\_\{\\mathrm\{in\}\}

endif

Augment nodes and features

Vrwd←Vin∪\(VΓ\+\|Vin\|\)V^\{\\mathrm\{rwd\}\}\\leftarrow V\_\{\\mathrm\{in\}\}\\cup\(V\_\{\\Gamma\}\+\|V\_\{\\mathrm\{in\}\}\|\)

XΓ←LiftFeatures​\(Xin,ϕ,VΓ\)X\_\{\\Gamma\}\\leftarrow\\textsc\{LiftFeatures\}\(X\_\{\\mathrm\{in\}\},\\phi,V\_\{\\Gamma\}\)

Xrwd←\[Xin∥XΓ\]X^\{\\mathrm\{rwd\}\}\\leftarrow\[X\_\{\\mathrm\{in\}\}\\\|X\_\{\\Gamma\}\]

Augment edges

EΓ↑←\{\(a\+\|Vin\|,b\+\|Vin\|\):\(a,b\)∈EΓ\}E\_\{\\Gamma\}^\{\\uparrow\}\\leftarrow\\\{\(a\+\|V\_\{\\mathrm\{in\}\}\|,b\+\|V\_\{\\mathrm\{in\}\}\|\):\(a,b\)\\in E\_\{\\Gamma\}\\\}

Ecpl←\{\(u,ϕ\(u\)\+\|Vin\|\),\(ϕ\(u\)\+\|Vin\|,u\):u∈Vin\}E\_\{\\mathrm\{cpl\}\}\\leftarrow\\\{\(u,\\phi\(u\)\+\|V\_\{\\mathrm\{in\}\}\|\),\(\\phi\(u\)\+\|V\_\{\\mathrm\{in\}\}\|,u\):u\\in V\_\{\\mathrm\{in\}\}\\\}

Erwd←Ein∪EΓ↑∪EcplE^\{\\mathrm\{rwd\}\}\\leftarrow E\_\{\\mathrm\{in\}\}\\cup E\_\{\\Gamma\}^\{\\uparrow\}\\cup E\_\{\\mathrm\{cpl\}\}

Edge weights

wrwd​\(e\)←1∀e∈Ein∪EΓ↑w^\{\\mathrm\{rwd\}\}\(e\)\\leftarrow 1\\quad\\forall e\\in E\_\{\\mathrm\{in\}\}\\cup E\_\{\\Gamma\}^\{\\uparrow\}

wrwd​\(e\)←ϵ∀e∈Ecplw^\{\\mathrm\{rwd\}\}\(e\)\\leftarrow\\epsilon\\quad\\forall e\\in E\_\{\\mathrm\{cpl\}\}

return

Grwd=\(Vrwd,Erwd,Xrwd,wrwd\)G^\{\\mathrm\{rwd\}\}=\(V^\{\\mathrm\{rwd\}\},E^\{\\mathrm\{rwd\}\},X^\{\\mathrm\{rwd\}\},w^\{\\mathrm\{rwd\}\}\)

ForFindN,FiedlerRanking,LiftFeaturesandSchreierTransforminAlgorithm[1](https://arxiv.org/html/2607.27479#alg1)pseudocodes, refer to Appendix A\.8\.1\-A\.8\.3\.

##### Rewiring Strategy\.

A hierarchial communication layer is introduced, and it facilitates global information flow while preserving the sparse nature of the input graph\. The rewired graphGr​w​dG^\{rwd\}is constructed asAlgorithm[1](https://arxiv.org/html/2607.27479#alg1):

- •We generate an auxiliary 4\-regular Schreier\-Coset graphΓ=\(VΓ,EΓ\)\\Gamma=\(V\_\{\\Gamma\},E\_\{\\Gamma\}\)\.
- •We establish mappingϕ:Vi​n→VΓ\\phi:V\_\{in\}\\to V\_\{\\Gamma\}using Fiedler rankings to ensure nodes are coupled based on their global connectivity\.
- •We then define the augmented edge setEr​w​dE^\{rwd\}by concatenating the original, augmented and coupling layer\.

Here,Ei​nE\_\{in\}: original input edges to maintain local inductive bias\),EΓ↑E\_\{\\Gamma\}^\{\\uparrow\}: 4\-regular expander edges shifted to auxiliary nodes\.Ec​p​lE\_\{cpl\}: bidirectional edges betweenu∈Vi​nu\\in V\_\{in\}and its mapped cosetϕ​\(u\)∈VΓ\\phi\(u\)\\in V\_\{\\Gamma\}\. The rewired graph is defined over the augmented vertex setVr​w​d=Vi​n∪VΓV^\{rwd\}=V\_\{in\}\\cup V\_\{\\Gamma\}:Gr​w​d=\(Vr​w​d,Er​w​d\),Er​w​d=Ei​n∪EΓ↑∪Ec​p​lG^\{rwd\}=\(V^\{rwd\},E^\{rwd\}\),\\quad E^\{rwd\}=E\_\{in\}\\cup E\_\{\\Gamma\}^\{\\uparrow\}\\cup E\_\{cpl\}\. The augmented edges are weighted according to their layer:we=1,∀e∈Ei​n∪EΓ↑;we=ϵ,∀e∈Ec​p​lw\_\{e\}=1,\\forall e\\in E\_\{in\}\\cup E\_\{\\Gamma\}^\{\\uparrow\};\\quad w\_\{e\}=\\epsilon,\\forall e\\in E\_\{cpl\}whereϵ\>0\\epsilon\>0is a global strength parameter regulating the influence of the global communication layer\.

As formulated inArnaiz\-Rodriguez and Errica \([2025](https://arxiv.org/html/2607.27479#bib.bib24)\)theover\-squashingphenomenon has two components, topological complexity and computational bottlenecks\. TheSCGRmethod rests on three key pillars: \(i\) locality preservation through spectral embeddings, \(ii\) effective resistance reduction via alternative low\-resistance pathways, and \(iii\) quantifiable over\-squashing mitigation while maintaining competitive accuracy\. Now, we first analyze the computational complexity of the approach\. The practical implementation ofSCGRinvolves several computational components, each with well\-defined complexity bounds\.

Graph Construction:The Schreier\-coset graphΓ\\GammahasVΓ=O​\(n\)V\_\{\\Gamma\}=O\(n\)vertices for\(modn\)\\pmod\{n\}\(andO​\(n⋅polylog​\(n\)\)O\(n\\cdot\\mathrm\{polylog\}\(n\)\)in general case\), with constant degreed=\|𝕊\|=4d=\|\\mathbb\{S\}\|=4\. Its edge set therefore satisfies\|EΓ\|=O​\(\|VΓ\|\)\|E\_\{\\Gamma\}\|=O\(\|V\_\{\\Gamma\}\|\)\. ConstructingΓ\\Gammavia coset representatives and generator multiplications requiresO​\(\|VΓ\|\)O\(\|V\_\{\\Gamma\}\|\)group operations, which can be cached once and reused across multiple input graphs\.

Mapping and Rewiring:The spectral mappingϕ:Vi​n→VΓ\\phi:V\_\{in\}\\to V\_\{\\Gamma\}is computed using the Fiedler vector of the normalized Laplacian for the input and Schreier graphs\. This needsO​\(T⋅\|E\|\)O\(T\\cdot\|E\|\)operations viaTTiterations of power method\. The augmentation process is strictly linear, involves couplings betweenuuandϕ​\(u\)\\phi\(u\), avoiding any quadratic distance over node pairs\.

Message Passing:Each GNN layer on the rewired graph requiresO​\(\|Er​w​d\|\)O\(\|E^\{rwd\}\|\)operations\. SinceEr​w​d=\|Ei​n\|\+\|EΓ\|\+\|Ec​p​l\|E^\{rwd\}=\|E\_\{in\}\|\+\|E\_\{\\Gamma\}\|\+\|E\_\{cpl\}\|, and the Schreier graphΓ\\Gammais a d\-regular expander \(d=4d=4\), the auxiliary edge count is2​\|VΓ\|2\|V\_\{\\Gamma\}\|\. The total edge complexity isO​\(\|Ei​n\|\+\|Vi​n\|\)O\(\|E\_\{in\}\|\+\|V\_\{in\}\|\), ensuring per\-layer computational overhead remains near\-linear in the input size\.

Space Complexity:The node set isVr​w​d=Vi​n∪VΓV^\{rwd\}=V\_\{in\}\\cup V\_\{\\Gamma\}where\|VΓ\|≈\|Vi​n\|\|V\_\{\\Gamma\}\|\\approx\|V\_\{in\}\|is chosen dynamically to ensure coverage\. The total number of edges added\(\|Ei​n\|\+\|Ec​p​l\)\(\|E\_\{in\}\|\+\|E\_\{cpl\}\)scales linearly asO​\(\|Vi​n\|\)O\(\|V\_\{in\}\|\)due to the constant degree of the Schreier generators\(d=4\)\(d=4\)and the one to one nature of the spectral coupling\. This leads to memory overhead which is sub\-quadratic\.

## 4Theoretical Properties of SCGR

We first show that the Schreier\-coset graphsΓp\\Gamma\_\{p\}for odd primes form an expander family with strong spectral and mixing properties; enabling efficient information propagation through low ER paths\.

###### Lemma 4\.1\(Uniform Spectral Gap\)\.

For primesp≥3p\\geq 3, let𝒢p=SL⁡\(2,𝔽p\)\\mathcal\{G\}\_\{p\}=\\operatorname\{SL\}\(2,\\mathbb\{F\}\_\{p\}\)and let𝕊p⊆𝒢p\\mathbb\{S\}\_\{p\}\\subseteq\\mathcal\{G\}\_\{p\}be the generating set𝕊p=\{\(1±101\),\(10±11\)\}\\mathbb\{S\}\_\{p\}=\\left\\\{\\begin\{pmatrix\}1&\\pm 1\\\\ 0&1\\end\{pmatrix\},\\begin\{pmatrix\}1&0\\\\ \\pm 1&1\\end\{pmatrix\}\\right\\\}, andHp≤𝒢pH\_\{p\}\\leq\\mathcal\{G\}\_\{p\}be the diagonal determinant\-one subgroup\. Then there existsγ0\>0\\gamma\_\{0\}\>0independent ofppsuch that the Schreier\-coset graphsΓp\\Gamma\_\{p\}on the left cosets𝒢p/Hp\\mathcal\{G\}\_\{p\}/H\_\{p\}satisfy

1−maxλ≠1⁡\|λ​\(PΓp\)\|≥γ0,1\-\\max\_\{\\lambda\\neq 1\}\|\\lambda\(P\_\{\\Gamma\_\{p\}\}\)\|\\geq\\gamma\_\{0\},wherePΓpP\_\{\\Gamma\_\{p\}\}is the transition matrix of the random walk onΓp\\Gamma\_\{p\}and the maximum ranges over its eigenvaluesλ≠1\\lambda\\neq 1\.

###### Lemma 4\.2\(Expander Mixing\)\.

For primesp≥3p\\geq 3and allt≥0t\\geq 0, the random walk matrixPΓpP\_\{\\Gamma\_\{p\}\}on a Schreier\-coset graphΓp\\Gamma\_\{p\}with uniform spectral gapγ0\\gamma\_\{0\}satisfies

\|\(PΓpt\)i​v−1\|VΓp\|\|≤\(1−γ0\)t\.\\left\|\(P\_\{\\Gamma\_\{p\}\}^\{t\}\)\_\{iv\}\-\\frac\{1\}\{\|V\_\{\\Gamma\_\{p\}\}\|\}\\right\|\\leq\\left\(1\-\\gamma\_\{0\}\\right\)^\{t\}\.Ift≥log⁡\(2​\|VΓp\|\)γ0t\\geq\\frac\{\\log\(2\|V\_\{\\Gamma\_\{p\}\}\|\)\}\{\\gamma\_\{0\}\}, then\(PΓpt\)i​v≥12​\|VΓp\|\(P\_\{\\Gamma\_\{p\}\}^\{t\}\)\_\{iv\}\\geq\\frac\{1\}\{2\|V\_\{\\Gamma\_\{p\}\}\|\}\.

###### Lemma 4\.3\(Effective Resistance Bound\)\.

For any primep≥3p\\geq 3and verticesu,v∈VΓu,v\\in V\_\{\\Gamma\},

ReffΓp​\(u,v\)≤2d​γ0,R\_\{\\mathrm\{eff\}\}^\{\\Gamma\_\{p\}\}\(u,v\)\\leq\\frac\{2\}\{d\\gamma\_\{0\}\},whered=\|𝕊\|d=\|\\mathbb\{S\}\|is the degree andγ0\\gamma\_\{0\}is the uniform spectral gap\.

By bounding the effective resistance as a function of the uniform spectral gapγ0\\gamma\_\{0\}, Lemma[8\.3](https://arxiv.org/html/2607.27479#S8.Thmtheorem3)guarantees the Schreier\-coset family avoids structural bottlenecks, forming a strong communication backbone for the input graph\.

Locality Preservation via Spectral Embeddings\.The following result gives sufficient conditions under which the node–coset map preserves locality up to a controlled additive and multiplicative distortion\.

###### Theorem 4\.4\(Locality Control\)\.

Assume there exist constantscin<∞c\_\{\\mathrm\{in\}\}<\\inftyandcΓ\>0c\_\{\\Gamma\}\>0such thatΦin\\Phi\_\{\\mathrm\{in\}\}andΦΓ\\Phi\_\{\\Gamma\}satisfy

‖Φin​\(u\)−Φin​\(v\)‖2≤cin​distin⁡\(u,v\)\\\|\\Phi\_\{\\mathrm\{in\}\}\(u\)\-\\Phi\_\{\\mathrm\{in\}\}\(v\)\\\|\_\{2\}\\leq c\_\{\\mathrm\{in\}\}\\operatorname\{dist\}\_\{\\mathrm\{in\}\}\(u,v\)for everyu,v∈Vinu,v\\in V\_\{\\mathrm\{in\}\}and

‖ΦΓ​\(x\)−ΦΓ​\(y\)‖2≥cΓ​distΓ⁡\(x,y\)\\\|\\Phi\_\{\\Gamma\}\(x\)\-\\Phi\_\{\\Gamma\}\(y\)\\\|\_\{2\}\\geq c\_\{\\Gamma\}\\operatorname\{dist\}\_\{\\Gamma\}\(x,y\)for everyx,y∈ϕ​\(Vin\)x,y\\in\\phi\(V\_\{\\mathrm\{in\}\}\)\. If‖ΦΓ​\(ϕ​\(v\)\)−Φin​\(v\)‖2≤ϵ\\\|\\Phi\_\{\\Gamma\}\(\\phi\(v\)\)\-\\Phi\_\{\\mathrm\{in\}\}\(v\)\\\|\_\{2\}\\leq\\epsilonfor everyvv, then

distΓ⁡\(ϕ​\(u\),ϕ​\(v\)\)≤cincΓ​distin⁡\(u,v\)\+2​ϵcΓ\.\\operatorname\{dist\}\_\{\\Gamma\}\(\\phi\(u\),\\phi\(v\)\)\\leq\\frac\{c\_\{\\mathrm\{in\}\}\}\{c\_\{\\Gamma\}\}\\operatorname\{dist\}\_\{\\mathrm\{in\}\}\(u,v\)\+\\frac\{2\\epsilon\}\{c\_\{\\Gamma\}\}\.

While the metric assumptions in Theorem[8\.4](https://arxiv.org/html/2607.27479#S8.Thmtheorem4)can be restrictive for arbitrary graphs, they provide a sufficient condition for the node\-coset map to preserve locality\. This motivates thespectral\_mapstrategy\. Laplacian eigenmaps minimize Dirichlet energy and hence favor embeddings that vary smoothly across adjacent vertices\. On the other hand,FiedlerRankingaligns the vertices according to their positions along a spectral coordinate, yielding an approximate preservation of locality structure\. However, neither the upper and lower Lipschitz bounds nor the uniform alignment condition is guaranteed\. The theorem should thus be viewed as a conditional guarantee, while Fiedler rank matching serves as a practical heuristic\.

##### Effective Resistance Analysis of the Rewired Graph\.

Theorem[8\.5](https://arxiv.org/html/2607.27479#S8.Thmtheorem5)shows that the coupling adds a low\-resistance bypass viaΓ\\Gamma, reducingReffR\_\{\\mathrm\{eff\}\}for distant pairs and improving long\-range information flow\.

###### Theorem 4\.5\(Effective Resistance in Rewired Graph\)\.

InGrwdG^\{\\mathrm\{rwd\}\}, for anyu,v∈Vinu,v\\in V\_\{\\mathrm\{in\}\},

Reffrwd​\(u,v\)≤min⁡\{Reffin​\(u,v\),ReffΓ​\(ϕ​\(u\),ϕ​\(v\)\)\+2ε\}\.R\_\{\\mathrm\{eff\}\}^\{\\mathrm\{rwd\}\}\(u,v\)\\leq\\min\\Big\\\{R\_\{\\mathrm\{eff\}\}^\{\\mathrm\{in\}\}\(u,v\),\\;R\_\{\\mathrm\{eff\}\}^\{\\Gamma\}\(\\phi\(u\),\\phi\(v\)\)\+\\frac\{2\}\{\\varepsilon\}\\Big\\\}\.

Viewing the augmented graph as an electrical network, Thomson’s principle ensures that the effective resistance cannot exceed the energy of a flow routed strictly through the original graph, givingReffinR\_\{\\mathrm\{eff\}\}^\{\\mathrm\{in\}\}, or routed strictly through theΓ\\Gamma\-layer, giving the right\-hand term\.

##### Information Flow and Over\-Squashing Mitigation\.

The connection between effective resistance and information propagation in neural networks is well established\. In message\-passing networks, the gradient flow between distant nodes is inversely proportional to their effective resistance\.

###### Theorem 4\.6\(Over\-Squashing Mitigation\)\.

For anyu,v∈Vinu,v\\in V\_\{\\mathrm\{in\}\}withu≠vu\\neq v,

ρ​\(u,v\):=Reffin​\(u,v\)Reffrwd​\(u,v\)≥max⁡\{1,Reffin​\(u,v\)ReffΓ​\(ϕ​\(u\),ϕ​\(v\)\)\+2ε\}\.\\rho\(u,v\):=\\frac\{R\_\{\\mathrm\{eff\}\}^\{\\mathrm\{in\}\}\(u,v\)\}\{R\_\{\\mathrm\{eff\}\}^\{\\mathrm\{rwd\}\}\(u,v\)\}\\geq\\max\\left\\\{1,\\;\\frac\{R\_\{\\mathrm\{eff\}\}^\{\\mathrm\{in\}\}\(u,v\)\}\{R\_\{\\mathrm\{eff\}\}^\{\\Gamma\}\(\\phi\(u\),\\phi\(v\)\)\+\\frac\{2\}\{\\varepsilon\}\}\\right\\\}\.

IfReffin​\(u,v\)R\_\{\\mathrm\{eff\}\}^\{\\mathrm\{in\}\}\(u,v\)grows rapidly with distance whileReffΓ​\(ϕ​\(u\),ϕ​\(v\)\)≤2d​γR\_\{\\mathrm\{eff\}\}^\{\\Gamma\}\(\\phi\(u\),\\phi\(v\)\)\\leq\\frac\{2\}\{d\\gamma\}is bounded, thenρ​\(u,v\)≳Reffin​\(u,v\)/\(2d​γ\+2ε\)\\rho\(u,v\)\\gtrsim\{R\_\{\\mathrm\{eff\}\}^\{\\mathrm\{in\}\}\(u,v\)\}/\(\{\\frac\{2\}\{d\\gamma\}\+\\frac\{2\}\{\\varepsilon\}\}\)can be very large\.

##### Performance Guarantees\.

While the previous theorems utilized single\-layer information flow to establish bounds on effective resistance, optimally splitting the gradient flow across both layers in parallel yields a tighter bound on the total resistance:

###### Theorem 4\.7\(Performance Guarantees\)\.

Suppose the transition matrices of random walks on the Schreier\-coset graphs satisfy

1−λ2​\(PΓp\)≥γ0\>01\-\\lambda\_\{2\}\(P\_\{\\Gamma\_\{p\}\}\)\\geq\\gamma\_\{0\}\>0uniformly inppand defineB0=2d​γ0\+2ϵB\_\{0\}=\\frac\{2\}\{d\\gamma\_\{0\}\}\+\\frac\{2\}\{\\epsilon\}\. Then for everyu,v∈Vinu,v\\in V\_\{\\mathrm\{in\}\}withu≠vu\\neq v,

Reffrwd​\(u,v\)≤Reffin​\(u,v\)​B0Reffin​\(u,v\)\+B0\.R\_\{\\mathrm\{eff\}\}^\{\\mathrm\{rwd\}\}\(u,v\)\\leq\\frac\{R\_\{\\mathrm\{eff\}\}^\{\\mathrm\{in\}\}\(u,v\)B\_\{0\}\}\{R\_\{\\mathrm\{eff\}\}^\{\\mathrm\{in\}\}\(u,v\)\+B\_\{0\}\}\.Consequently,

ρ​\(u,v\)≥1\+Reffin​\(u,v\)B0\.\\rho\(u,v\)\\geq 1\+\\frac\{R\_\{\\mathrm\{eff\}\}^\{\\mathrm\{in\}\}\(u,v\)\}\{B\_\{0\}\}\.

These results make the impact of SCGR*dimension\-free*: the post\-wiring resistance between any two nodes is capped by the expander parametersddandγ0\\gamma\_\{0\}and the couplingε\\varepsilon, bypassing the input graph’s topology\. By explicitly bounding the improvement factorρ​\(u,v\)\\rho\(u,v\), we quantify how SCGR collapses the long\-range bottlenecks responsible for over\-squashing\. Crucially, because theΓ\\Gamma\-overlay is constant\-degree, these long\-range communication guarantees are achieved with*near\-linear*computational overhead\.

All proofs are provided in the Appendix\.

## 5Experiments

The efficacy ofSCGRis validated extensively on diverse node and graph classification benchmarks\. We also conduct experiments on stochastic block models with controllable modularity to demonstratingSCGR’s behavior across different community structures\. The tests are run on Nvidia A100 GPU\.

### 5\.1Node Classification

We predict the label of individual nodes given a graph, node features and a subset of labeled nodes\. The task: labels are available only for a portion of the nodes, and the model must leverage both local features and graph structures to infer the labels of remaining nodes\. For Node Classification, we use:Amazon Computers & Photo,CoAuthor CS\(Shchuret al\.,[2018](https://arxiv.org/html/2607.27479#bib.bib27)\),CiteSeer,Cora & PubMed\(Senet al\.,[2008](https://arxiv.org/html/2607.27479#bib.bib28)\)datasets\.

Each model is trained withepochs: 200, layers: 4,hidden dimension: 256 and dropout rate: 0\.5following the hyperparameters \(referAppendix\. A\.8\.5,Palowitch and Perozzi \([2019](https://arxiv.org/html/2607.27479#bib.bib50)\)\)\. All experiments are repeated 20 times to ensure statistical robustness\. Comparisons are made against standard baseline models includingLogReg\(Chapelleet al\.,[2009](https://arxiv.org/html/2607.27479#bib.bib32)\),MLP\(Werbos,[1974](https://arxiv.org/html/2607.27479#bib.bib29)\),GAT\(Veličkovićet al\.,[2017](https://arxiv.org/html/2607.27479#bib.bib12)\),GCN\(Kipf,[2017](https://arxiv.org/html/2607.27479#bib.bib11)\),MoNET\(Palowitch and Perozzi,[2019](https://arxiv.org/html/2607.27479#bib.bib50)\),LabelProp\(Zhu and Ghahramani,[2003](https://arxiv.org/html/2607.27479#bib.bib51)\),GraphSage\(GS\)\-variants\(Hamiltonet al\.,[2017b](https://arxiv.org/html/2607.27479#bib.bib52)\)\. Given that the benchmark datasets exhibit balanced class distributions, test accuracy is adopted as the primary evaluation metric, reported inTable[1](https://arxiv.org/html/2607.27479#S5.T1)\.

Table 1:Performance comparison of SCGR against baseline models across six standard benchmark datasets \(Graph\-rewiring methods are omitted, as they report only graph\-classification results on these benchmarks\.\)*SCGR*achieves the highest accuracy on four of the six benchmark datasets, with notable improvements inAmazon Computers, Amazon Photo, Coauthor\-CS,PubMedand is competent inCora\. The consistent performance gains across most datasets, combined with reduced variance suggest that*SCGR*provides a robust enhancement to existing GNN architectures\. The method’s effectiveness is particularly pronounced on the Amazon datasets and Computer Science, where the spectral properties and community structure align well with the Schreier\-coset graph’s expander properties, enabling more effective long\-range information propagation during message passing\. SCGR’s weaker performance onCiteSeerstems from the dataset’s properties: high inter\-to\-intra\-class edge ratio, sparse noisy features, and many isolated nodes, which make Fiedler\-vector alignment unreliable and introduce misdirected coupling edges\. This reflects a general limitation of spectral alignment rather than SCGR specifically\.

### 5\.2Graph Classification

In Graph classification, we predict a single label for an entire graph by leveraging its structural information and associated node or edge features\. We use theTU Dataset\(Morriset al\.,[2020](https://arxiv.org/html/2607.27479#bib.bib45)\), which comprises of over 120 graph classification and regression datasets\. Representative datasets included in our experimentation are: chemical graphs \(MUTAG\), protein structures \(PROTEINS\), social networks \(IMDB\-BINARY, REDDIT\-BINARY\), and research collaboration graphs \(COLLAB\)\. The topology of the graphs about the task is identified as requiring long\-range interactions\.SCGRis compared againstCGP\(Wilsonet al\.,[2024](https://arxiv.org/html/2607.27479#bib.bib16)\),EGP\(Deacet al\.,[2022](https://arxiv.org/html/2607.27479#bib.bib15)\),FA\(Alon and Milman,[1984](https://arxiv.org/html/2607.27479#bib.bib33)\),DIGL\(Gasteigeret al\.,[2019](https://arxiv.org/html/2607.27479#bib.bib30)\),SDRF\(Toppinget al\.,[2021](https://arxiv.org/html/2607.27479#bib.bib34)\),FoSR\(Karhadkaret al\.,[2023](https://arxiv.org/html/2607.27479#bib.bib18)\),BORF\(Nguyenet al\.,[2023](https://arxiv.org/html/2607.27479#bib.bib31)\)andGTR\(Blacket al\.,[2023](https://arxiv.org/html/2607.27479#bib.bib19)\)\.

Each model is trained with a train/val/test split of 80%\\%/10%\\%/10%\\%and the following parametersepochs: 100, layers: 5, hidden dimension: 128, dropout: 0\.5, weight decay: 0\.0005\. Accuracy is the primary metric comparison\.

Each experiment is run 20 times for statistical robustness\.

Table 2:Results of SCGR compared against multiple models\. OOT indicates out\-of\-time and OOM points to out\-of\-memory error\. The colors highlightFirst,SecondandThirdpositions respectively\.InTable[2](https://arxiv.org/html/2607.27479#S5.T2)SCGRconsistently achieves strong performance across the*TU Dataset*in both*GCN \+ SCGR*and*GIN \+ SCGR*configurations\. Schreier\-coset attains first place in six of the twelve configurations and shows competitive scores in ten datasets by being in the top 3\. Notably inEnzymesdataset, it outperforms all models inGCN \+ SCGRand attains a significant gain of8%inGIN \+ SCGR\. OnREDDIT,SCGRattains first and second place respectively \(vice\-versa for IMDB\)\.SCGR’sstrong performance across diverse graphical datasets underscores its diverse applications\.

![Refer to caption](https://arxiv.org/html/2607.27479v1/Figures/er_dumbbell_3x2_with_legendpanel.png)Figure 2:Effective Resistance \(ER\) across benchmarks:GCN/GIN \+ SCGRcompared toGCN/GINbaselines across varying graph complexities\.Figure[2](https://arxiv.org/html/2607.27479#S5.F2), empirically validates consistent reductions in effective resistance across all benchmark datasets\.SCGRachieves the most substantial improvements on IMDB\-BINARY :41%41\\%reduction, COLLAB:23−30%23\-30\\%reduction and MUTAG:34%34\\%reduction, where long\-range dependencies are particularly critical\. Even on datasets with inherently good connectivity like PROTEINS,SCGRstill provides meaningful improvements\. These results confirm thatSCGRsuccessfully creates more efficient information propagation pathways, directly addressing the over\-squashing\.For ER values,refer: Appendix\. 8\.5\.2

For, molecular prediction task,SCGRis assessed on theOpen Graph Benchmark \- Graph PredictionOgbg\-MolhivandOgbg\-MolpcbadatasetsHuet al\.\([2020](https://arxiv.org/html/2607.27479#bib.bib43)\)\. The experimental protocol adheres to the implementation and hyperparameter configuration specified byHuet al\.\([2020](https://arxiv.org/html/2607.27479#bib.bib43)\)\.

Table 3, in Appendix\. 8\.5\.4reportsROC\-AUC%metrics on the Ogbg\-Molhiv andAverage Precision \(AP\)Ogbg\-Molpcba dataset\.SCGRexhibits robust predictive performance while maintaining high structural fidelity\. Schreier\-coset in both configurations attains highest ROC\-AUC score in Molhiv dataset\. For the Molpcba dataset,GCN\+SCGRattains the highest average precision, withGIN\+SCGRremaining competitive based on the inherent scale and structural complexity of Molpcba\.

We further evaluate SCGR on thePeptides\-FuncandPeptides\-Structdatasets from the Long Range Graph Benchmark, using test AP and MAE, respectively\. SCGR achieves the best performance across both GCN and GIN, with GIN\+SCGR improving AP by \(13\.4%\) and reducing MAE by \(9\.2%\) relative to the strongest baseline\. Full results are reported inAppendix 8\.5\.5

### 5\.3Graph Modularity

Using the Stochastic Block Models \(SBM\)Lee and Wilkinson \([2019](https://arxiv.org/html/2607.27479#bib.bib42)\)with 50 equal communities \(1000 nodes\)\. Intra\- and inter\-community edge probabilities \(pi​n,po​u​tp\_\{in\},p\_\{out\}\) are varied to control modularity, withpi​n\>po​u​tp\_\{in\}\>p\_\{out\}ensuring meaningful structure\. This design enables systematic analysis of SCGR performance in weak\-to\-strong community regimes\. The classification task involves predicting community membership, directly testing the model’s ability to capture long\-range dependencies\.

![Refer to caption](https://arxiv.org/html/2607.27479v1/Figures/sbms-2.png)Figure 3:Comparison of effective resistance across different SBM modularities\.Figure[3](https://arxiv.org/html/2607.27479#S5.F3)reports an inverse correlation between graph modularity andSCGRimprovements\. The largest gains occur in low\-modularity graphs, where weak community structure induces connectivity bottlenecks with a reduction of41\.1%41\.1\\%in effective resistance\. Gains decrease with increasing modularity \(\+0\.79% medium, \+0\.20% high\), as classification becomes dominated by local neighborhood information\. SCGR continues to provide a low resistance pathway\. SCGR is most effective in regimes requiring long\-range information propagation, where standard message passing is limited by over\-squashing\. \(referAppendix\. 8\.5\.3in the Appendix for ER value for varying modularity\.\)

## 6Ablation Study

We validate SCGR’s three design pillars through systematic ablations on graph classification \(Appendix\. 8\.6\.1\) and node classification \(Appendix\. 8\.6\.2\)\.\(1\) Expander structure:Replacing theSL​\(2,ℤn\)\\text\{SL\}\(2,\\mathbb\{Z\}\_\{n\}\)Schreier\-Coset graph with a random 4\-regular graph degrades accuracy by5\.26%5\.26\\%on MUTAG and2\.8%2\.8\\%on Amazon Photo, confirming that algebraic symmetry provides guarantees beyond mere connectivity\.\(2\) Spectral alignment:Random node\-to\-coset mapping under\-performs Fiedler\-based alignment by6\.05%6\.05\\%on MUTAG and2\.9%2\.9\\%on Amazon Photo, on COLLAB, spectral alignment achieves71\.1%71\.1\\%lowerReffR\_\{\\text\{eff\}\}than random mapping\.\(3\) Coupling strength:Performance peaks atϵ=1\.0\\epsilon=1\.0across both tasks—on Amazon Photo,ϵ=1\.0\\epsilon=1\.0achieves94\.0%94\.0\\%versus92\.3%92\.3\\%atϵ=0\.1\\epsilon=0\.1\.

## 7Conclusion

We introduce Schreier\-Coset Graph Rewiring\(SCGR\), principled graph\-rewiring framework that alleviates over\-squashing in GNNs\. Using the spectral properties of Schreier\-Coset graph derived fromS​L​\(2,ℤn\)SL\(2,\\mathbb\{Z\}\_\{n\}\)we have established an uniform upper bound on effective resistance\.ReffΓ​\(u,v\)≤2d​γ0R\_\{\\mathrm\{eff\}\}^\{\\Gamma\}\(u,v\)\\leq\\frac\{2\}\{d\\gamma\_\{0\}\}\. As a result, distant node pairs\-most affected by over\-squashing experience the largest reductions\. Empirically,SCGRreduces effective resistance by15−40%15\-40\\%across benchmark datasets while maintaining a competitive accuracy\. In SBM graphs, where modularity varies,SCGRgains are the strongest in lower\-modularity graphs\+7\.55%\+7\.55\\%and remain stable in highly modular paradigms\.SCGRachieves these improvement with complexity of\|Ei​n\|\+\|Vi​n\|\|E\_\{in\}\|\+\|V\_\{in\}\|offering a theoretically rich solution to over\-squashing\. From our ablation, we concludeε=1\.0\\varepsilon=1\.0is effective to capture local and global properties, further iterations could incorporate a differentiableε\\varepsilonor optimization to dynamically tailor the communication layer to specific topological bottlenecks in real time\.

## References

- N\. Alon and V\. D\. Milman \(1984\)Eigenvalues, expanders and superconcentrators\.In25th Annual Symposium onFoundations of Computer Science, 1984\.,pp\. 320–322\.Cited by:[§5\.2](https://arxiv.org/html/2607.27479#S5.SS2.p1.1)\.
- U\. Alon and E\. Yahav \(2021\)On the bottleneck of graph neural networks and its practical implications\.ICLR 2021, arXiv:2006\.05205\.Cited by:[§1](https://arxiv.org/html/2607.27479#S1.p2.1)\.
- A\. Arnaiz\-Rodriguez and F\. Errica \(2025\)Oversmoothing," oversquashing", heterophily, long\-range, and more: demystifying common beliefs in graph machine learning\.Neurips 2025 arXiv:2505\.15547\.Cited by:[§1](https://arxiv.org/html/2607.27479#S1.p2.1),[§1](https://arxiv.org/html/2607.27479#S1.p5.1),[§3\.1](https://arxiv.org/html/2607.27479#S3.SS1.SSS0.Px2.p2.1)\.
- H\. Attali, D\. Buscaldi, and N\. Pernelle \(2024\)Delaunay graph: addressing over\-squashing and over\-smoothing using delaunay triangulation\.InForty\-first International Conference on Machine Learning,Cited by:[§1\.1](https://arxiv.org/html/2607.27479#S1.SS1.p1.1),[§1](https://arxiv.org/html/2607.27479#S1.p4.1)\.
- P\. W\. Battaglia, J\. B\. Hamrick, V\. Bapst, A\. Sanchez\-Gonzalez, V\. Zambaldi, M\. Malinowski, A\. Tacchetti, D\. Raposo, A\. Santoro, R\. Faulkner,et al\.\(2018\)Relational inductive biases, deep learning, and graph networks\.arXiv preprint arXiv:1806\.01261\.Cited by:[§1](https://arxiv.org/html/2607.27479#S1.p1.1)\.
- R\. v\. d\. Berg, T\. N\. Kipf, and M\. Welling \(2017\)Graph convolutional matrix completion\.arXiv preprint arXiv:1706\.02263\.Cited by:[§1](https://arxiv.org/html/2607.27479#S1.p1.1)\.
- M\. Black, Z\. Wan, A\. Nayyeri, and Y\. Wang \(2023\)Understanding oversquashing in gnns through the lens of effective resistance\.InInternational Conference on Machine Learning,pp\. 2528–2547\.Cited by:[§1\.1](https://arxiv.org/html/2607.27479#S1.SS1.p1.1),[§1](https://arxiv.org/html/2607.27479#S1.p3.3),[§5\.2](https://arxiv.org/html/2607.27479#S5.SS2.p1.1)\.
- J\. Bourgain and A\. Gamburd \(2008\)Uniform expansion bounds for cayley graphs of\.Annals of Mathematics,pp\. 625–642\.Cited by:[§8\.3\.1](https://arxiv.org/html/2607.27479#S8.SS3.SSS1.1.p1.7)\.
- D\. Braess \(1968\)Über ein paradoxon aus der verkehrsplanung\.Unternehmensforschung12\(1\),pp\. 258–268\.Cited by:[§1\.1](https://arxiv.org/html/2607.27479#S1.SS1.p1.1)\.
- E\. Breuillard, B\. J\. Green, R\. M\. Guralnick, and T\. Tao \(2015\)Expansion in finite simple groups of lie type\.Journal of the European Mathematical Society17\(6\),pp\. 1367–1434\.Cited by:[§8\.3\.1](https://arxiv.org/html/2607.27479#S8.SS3.SSS1.2.p2.3)\.
- D\. Cai, X\. Chen, and P\. Peng \(2023\)Effective resistances in non\-expander graphs\.arXiv preprint arXiv:2307\.01218\.Cited by:[§8\.3\.3](https://arxiv.org/html/2607.27479#S8.SS3.SSS3.1.p1.4)\.
- O\. Chapelle, B\. Scholkopf, and A\. Zien \(2009\)Semi\-supervised learning \(chapelle, o\. et al\., eds\.; 2006\)\[book reviews\]\.IEEE Transactions on Neural Networks20\(3\),pp\. 542–542\.Cited by:[§5\.1](https://arxiv.org/html/2607.27479#S5.SS1.p2.1)\.
- J\. Choi, S\. Park, H\. Wi, S\. Cho, and N\. Park \(2024\)Panda: expanded width\-aware message passing beyond rewiring\.IN ICLR arXiv:2406\.03671\.Cited by:[§1\.1](https://arxiv.org/html/2607.27479#S1.SS1.p1.1)\.
- A\. Deac, M\. Lackenby, and P\. Veličković \(2022\)Expander graph propagation\.InLearning on Graphs Conference,pp\. 38–1\.Cited by:[§1\.1](https://arxiv.org/html/2607.27479#S1.SS1.p1.1),[§1](https://arxiv.org/html/2607.27479#S1.p3.3),[§5\.2](https://arxiv.org/html/2607.27479#S5.SS2.p1.1)\.
- R\. Diestel \(2012\)Graph theory: springer graduate text gtm 173\.Vol\.173,Reinhard Diestel\.Cited by:[§1](https://arxiv.org/html/2607.27479#S1.p1.1)\.
- M\. Eliasof, F\. Frasca, B\. Bevilacqua, E\. Treister, G\. Chechik, and H\. Maron \(2023\)Graph positional encoding via random feature propagation\.InInternational Conference on Machine Learning,pp\. 9202–9223\.Cited by:[§1](https://arxiv.org/html/2607.27479#S1.p3.3)\.
- L\. Fesser and M\. Weber \(2024\)Mitigating over\-smoothing and over\-squashing using augmentations of forman\-ricci curvature\.InLearning on Graphs Conference,pp\. 19–1\.Cited by:[§1](https://arxiv.org/html/2607.27479#S1.p3.3)\.
- B\. Finkelshtein, X\. Huang, M\. Bronstein, and I\. I\. Ceylan \(2024\)Cooperative graph neural networks\.In ICML arXiv:2310\.01267\.Cited by:[§1\.1](https://arxiv.org/html/2607.27479#S1.SS1.p1.1)\.
- J\. Gasteiger, S\. Weißenberger, and S\. Günnemann \(2019\)Diffusion improves graph learning\.Advances in neural information processing systems32\.Cited by:[§5\.2](https://arxiv.org/html/2607.27479#S5.SS2.p1.1)\.
- J\. Gilmer, S\. S\. Schoenholz, P\. F\. Riley, O\. Vinyals, and G\. E\. Dahl \(2017\)Neural message passing for quantum chemistry\.InInternational conference on machine learning,pp\. 1263–1272\.Cited by:[§1](https://arxiv.org/html/2607.27479#S1.p1.1)\.
- W\. Hamilton, Z\. Ying, and J\. Leskovec \(2017a\)Inductive representation learning on large graphs\.Advances in neural information processing systems30\.Cited by:[§1](https://arxiv.org/html/2607.27479#S1.p1.1)\.
- W\. L\. Hamilton, R\. Ying, and J\. Leskovec \(2017b\)Inductive representation learning on large graphs\.CoRRabs/1706\.02216\.External Links:[Link](http://arxiv.org/abs/1706.02216),1706\.02216Cited by:[§5\.1](https://arxiv.org/html/2607.27479#S5.SS1.p2.1)\.
- F\. Harary \(1969\)Graph theory addison\-wesley reading ma usa\.HARTIGAN, JA: Clustering Algorithm\.Cited by:[§1](https://arxiv.org/html/2607.27479#S1.p1.1)\.
- H\. He, X\. Yu, J\. Zhang, S\. Song, and K\. B\. Letaief \(2023\)Message passing meets graph neural networks: a new paradigm for massive mimo systems\.IEEE Transactions on Wireless Communications23\(5\),pp\. 4709–4723\.Cited by:[§1](https://arxiv.org/html/2607.27479#S1.p2.1)\.
- S\. Hoory, N\. Linial, and A\. Wigderson \(2006\)Expander graphs and their applications\.Bulletin of the American Mathematical Society43\(4\),pp\. 439–561\.Cited by:[§8\.3\.1](https://arxiv.org/html/2607.27479#S8.SS3.SSS1.4.p4.2)\.
- W\. Hu, M\. Fey, M\. Zitnik, Y\. Dong, H\. Ren, B\. Liu, M\. Catasta, and J\. Leskovec \(2020\)Open graph benchmark: datasets for machine learning on graphs\.Advances in neural information processing systems33,pp\. 22118–22133\.Cited by:[§5\.2](https://arxiv.org/html/2607.27479#S5.SS2.p6.1),[§8\.5\.4](https://arxiv.org/html/2607.27479#S8.SS5.SSS4.p1.1)\.
- A\. Jamadandi, C\. Rubio\-Madrigal, and R\. Burkholz \(2024\)Spectral graph pruning against over\-squashing and over\-smoothing\.Advances in Neural Information Processing Systems37,pp\. 10348–10379\.Cited by:[§1\.1](https://arxiv.org/html/2607.27479#S1.SS1.p1.1)\.
- B\. Jiang, Z\. Zhang, D\. Lin, J\. Tang, and B\. Luo \(2019\)Semi\-supervised learning with graph learning\-convolutional networks\.InProceedings of the IEEE/CVF conference on computer vision and pattern recognition,pp\. 11313–11320\.Cited by:[§1](https://arxiv.org/html/2607.27479#S1.p2.1)\.
- K\. Karhadkar, P\. K\. Banerjee, and G\. Montúfar \(2023\)FoSR: first\-order spectral rewiring for addressing oversquashing in gnns\.ICLR 2023, arXiv:2210\.11790\.Cited by:[§1\.1](https://arxiv.org/html/2607.27479#S1.SS1.p1.1),[§1](https://arxiv.org/html/2607.27479#S1.p3.3),[§5\.2](https://arxiv.org/html/2607.27479#S5.SS2.p1.1)\.
- T\. Kipf \(2017\)Semi\-supervised classification with graph convolutional networks\.ICLR,2017 arXiv:1609\.02907\.Cited by:[§1](https://arxiv.org/html/2607.27479#S1.p2.1),[§5\.1](https://arxiv.org/html/2607.27479#S5.SS1.p2.1)\.
- H\. Y\. Koh, A\. T\. Nguyen, S\. Pan, L\. T\. May, and G\. I\. Webb \(2024\)Physicochemical graph neural network for learning protein–ligand interaction fingerprints from sequence data\.Nature Machine Intelligence6\(6\),pp\. 673–687\.Cited by:[§1](https://arxiv.org/html/2607.27479#S1.p1.1)\.
- C\. Lee and D\. J\. Wilkinson \(2019\)A review of stochastic block models and extensions for graph clustering\.Applied Network Science4\(1\),pp\. 1–50\.Cited by:[§5\.3](https://arxiv.org/html/2607.27479#S5.SS3.p1.2)\.
- Q\. Li, Z\. Han, and X\. Wu \(2018\)Deeper insights into graph convolutional networks for semi\-supervised learning\.InProceedings of the AAAI conference on artificial intelligence,Vol\.32\.Cited by:[§1](https://arxiv.org/html/2607.27479#S1.p5.1)\.
- L\. Liang, X\. Hu, Z\. Xu, Z\. Song, and I\. King \(2023a\)Predicting global label relationship matrix for graph neural networks under heterophily\.Advances in Neural Information Processing Systems36,pp\. 10909–10921\.Cited by:[§1](https://arxiv.org/html/2607.27479#S1.p5.1)\.
- L\. Liang, Z\. Xu, Z\. Song, I\. King, Y\. Qi, and J\. Ye \(2023b\)Tackling long\-tailed distribution issue in graph neural networks via normalization\.IEEE Transactions on Knowledge and Data Engineering36\(5\),pp\. 2213–2223\.Cited by:[§1](https://arxiv.org/html/2607.27479#S1.p5.1)\.
- C\. Morris, N\. M\. Kriege, F\. Bause, K\. Kersting, P\. Mutzel, and M\. Neumann \(2020\)Tudataset: a collection of benchmark datasets for learning with graphs\.arXiv preprint arXiv:2007\.08663\.Cited by:[§5\.2](https://arxiv.org/html/2607.27479#S5.SS2.p1.1)\.
- K\. Nguyen, N\. M\. Hieu, V\. D\. Nguyen, N\. Ho, S\. Osher, and T\. M\. Nguyen \(2023\)Revisiting over\-smoothing and over\-squashing using ollivier\-ricci curvature\.InInternational Conference on Machine Learning,pp\. 25956–25979\.Cited by:[§1\.1](https://arxiv.org/html/2607.27479#S1.SS1.p1.1),[§5\.2](https://arxiv.org/html/2607.27479#S5.SS2.p1.1)\.
- J\. Palowitch and B\. Perozzi \(2019\)MONET: debiasing graph embeddings via the metadata\-orthogonal training unit\.CoRRabs/1909\.11793\.External Links:[Link](http://arxiv.org/abs/1909.11793),1909\.11793Cited by:[§5\.1](https://arxiv.org/html/2607.27479#S5.SS1.p2.1)\.
- C\. Qian, A\. Manolache, K\. Ahmed, Z\. Zeng, G\. V\. d\. Broeck, M\. Niepert, and C\. Morris \(2024\)Probabilistically rewired message\-passing neural networks\.In ICLR arXiv:2310\.02156\.Cited by:[§1\.1](https://arxiv.org/html/2607.27479#S1.SS1.p1.1)\.
- A\. Sanchez\-Gonzalez, N\. Heess, J\. T\. Springenberg, J\. Merel, M\. Riedmiller, R\. Hadsell, and P\. Battaglia \(2018\)Graph networks as learnable physics engines for inference and control\.InInternational conference on machine learning,pp\. 4470–4479\.Cited by:[§1](https://arxiv.org/html/2607.27479#S1.p1.1)\.
- P\. Sen, G\. Namata, M\. Bilgic, L\. Getoor, B\. Galligher, and T\. Eliassi\-Rad \(2008\)Collective classification in network data\.AI magazine29\(3\),pp\. 93–93\.Cited by:[§5\.1](https://arxiv.org/html/2607.27479#S5.SS1.p1.1)\.
- O\. Shchur, M\. Mumme, A\. Bojchevski, and S\. Günnemann \(2018\)Pitfalls of graph neural network evaluation\.arXiv preprint arXiv:1811\.05868\.Cited by:[§5\.1](https://arxiv.org/html/2607.27479#S5.SS1.p1.1)\.
- D\. I\. Shuman, S\. K\. Narang, P\. Frossard, A\. Ortega, and P\. Vandergheynst \(2013\)The emerging field of signal processing on graphs: extending high\-dimensional data analysis to networks and other irregular domains\.IEEE signal processing magazine30\(3\),pp\. 83–98\.Cited by:[§1](https://arxiv.org/html/2607.27479#S1.p1.1)\.
- J\. Topping, F\. Di Giovanni, B\. P\. Chamberlain, X\. Dong, and M\. M\. Bronstein \(2021\)Understanding over\-squashing and bottlenecks on graphs via curvature\.arXiv preprint arXiv:2111\.14522\.Cited by:[§1\.1](https://arxiv.org/html/2607.27479#S1.SS1.p1.1),[§5\.2](https://arxiv.org/html/2607.27479#S5.SS2.p1.1)\.
- P\. Veličković, G\. Cucurull, A\. Casanova, A\. Romero, P\. Lio, and Y\. Bengio \(2017\)Graph attention networks\.ICLR 2018, arXiv:1710\.10903\.Cited by:[§1](https://arxiv.org/html/2607.27479#S1.p2.1),[§5\.1](https://arxiv.org/html/2607.27479#S5.SS1.p2.1)\.
- P\. Werbos \(1974\)Beyond regression: new tools for prediction and analysis in the behavioral sciences\.PhD thesis, Committee on Applied Mathematics, Harvard University, Cambridge, MA\.Cited by:[§5\.1](https://arxiv.org/html/2607.27479#S5.SS1.p2.1)\.
- J\. Wilson, M\. Bechler\-Speicher, and P\. Veličković \(2024\)Cayley graph propagation\.In Proceedings of the Third Learning on Graphs Conference, arXiv:2410\.03424\.Cited by:[§1](https://arxiv.org/html/2607.27479#S1.p3.3),[§5\.2](https://arxiv.org/html/2607.27479#S5.SS2.p1.1)\.
- X\. Zhu and Z\. Ghahramani \(2003\)Learning from labeled and unlabeled data with label propagation\.pp\.\.Cited by:[§5\.1](https://arxiv.org/html/2607.27479#S5.SS1.p2.1)\.

## 8Appendix\.

### 8\.1Summary

The*Appendix*contains mathematical formulation of the Schreier\-Coset Graphs\.

1. 1\.Section 8\.2:Preliminaries and Notations\.
2. 2\.Section 8\.3:Contains proofs for: 1. \(a\)Lemma 4\.1\- Spectral Gap as*A\.8\.3, Lemma 8\.1* 2. \(b\)Lemma 4\.2\- Expander Mixing as*A\.8\.3, Lemma 8\.2* 3. \(c\)Lemma 4\.3\- Effective Resistance Bound as*A\.8\.3, Lemma 8\.3* 4. \(d\)Theorem 4\.4\- Lipschitz Locality as*A\.8\.3, Theorem 8\.4* 5. \(e\)Theorem 4\.5\- Effective Resistance in Rewired GraphΓ\\Gammaas*A\.8\.3, Theorem 8\.5* 6. \(f\)Theorem 4\.6\- Over\-squashing Mitigation as*A\.8\.3, C\.8\.6*
3. 3\.Section 8\.4:Algorithm Functions 1. \(a\)8\.4\.1\-FindN 2. \(b\)8\.4\.2\-FiedlerRanking 3. \(c\)8\.4\.3\-LiftFeatures 4. \(d\)8\.4\.4\-SchreierTransform
4. 4\.Section 8\.5:Experiments 1. \(a\)8\.5\.1\- Hyper\-parameters 2. \(b\)8\.5\.2\- Effective Resistance: Benchmark Datasets 3. \(c\)8\.5\.3\- Effective Resistance: Stochastic Block Models 4. \(d\)8\.5\.4\- OGBG \- Molhiv, OGBG \- Molpcba 5. \(e\)8\.5\.5\- LRGB Peptides Struct and Peptides Func\.
5. 5\.Section 8\.6:Ablation Studies 1. \(a\)Section 8\.6\.1\- Node Classification 2. \(b\)Section 8\.6\.2\- Graph Classification

### 8\.2Preliminaries and Notations

Let𝒢\\mathcal\{G\}be a finitely generated group with identityee,H⊆𝒢H\\subseteq\\mathcal\{G\}a subgroup, and𝕊⊆𝒢\\mathbb\{S\}\\subseteq\\mathcal\{G\}a symmetric generating set \(s∈𝕊⇒s−1∈𝕊s\\in\\mathbb\{S\}\\Rightarrow s^\{\-1\}\\in\\mathbb\{S\}\)\. The quotient space𝒢/H=\{g​H:g∈𝒢\}\\mathcal\{G\}/H=\\\{gH:g\\in\\mathcal\{G\}\\\}consists of right cosets\.

##### The Schreier\-Coset Graph\.

The Schreier\-coset graphΓ=\(VΓ,EΓ\)\\Gamma=\(V\_\{\\Gamma\},E\_\{\\Gamma\}\)is defined by:

- •VΓ=\{g​H:g∈𝒢\}V\_\{\\Gamma\}=\\\{gH:g\\in\\mathcal\{G\}\\\}
- •EΓ=\{\{g​H,\(g​s\)​H\}:g​H∈VΓ,s∈𝕊\}E\_\{\\Gamma\}=\\\{\\\{gH,\(gs\)H\\\}:gH\\in V\_\{\\Gamma\},s\\in\\mathbb\{S\}\\\}

Γ\\Gammaisdd\-regular withd=\|𝕊\|d=\|\\mathbb\{S\}\|

##### Spectral Properties of the Schreier\-Coset Graph

LetAΓA\_\{\\Gamma\}denote the adjacency matrix ofΓ\\Gamma,DΓ=d​ID\_\{\\Gamma\}=dIthe degree matrix,LΓ=DΓ−AΓL\_\{\\Gamma\}=D\_\{\\Gamma\}\-A\_\{\\Gamma\}the Laplacian, and the transition matrixP=1d​AΓP=\\frac\{1\}\{d\}A\_\{\\Gamma\}\.

### 8\.3Theoretical Formulation and Proofs

#### 8\.3\.1Uniform Spectral Gap

###### Lemma 8\.1\(Uniform Spectral Gap\)\.

For primesp≥3p\\geq 3, let𝒢p=SL⁡\(2,𝔽p\)\\mathcal\{G\}\_\{p\}=\\operatorname\{SL\}\(2,\\mathbb\{F\}\_\{p\}\)and let𝕊p⊆𝒢p\\mathbb\{S\}\_\{p\}\\subseteq\\mathcal\{G\}\_\{p\}be the generating set𝕊p=\{\(1±101\),\(10±11\)\}\\mathbb\{S\}\_\{p\}=\\left\\\{\\begin\{pmatrix\}1&\\pm 1\\\\ 0&1\\end\{pmatrix\},\\begin\{pmatrix\}1&0\\\\ \\pm 1&1\\end\{pmatrix\}\\right\\\}, andHp≤𝒢pH\_\{p\}\\leq\\mathcal\{G\}\_\{p\}be the diagonal determinant\-one subgroup\. Then there existsγ0\>0\\gamma\_\{0\}\>0independent ofppsuch that the Schreier\-coset graphsΓp\\Gamma\_\{p\}on the left cosets𝒢p/Hp\\mathcal\{G\}\_\{p\}/H\_\{p\}satisfy

1−maxλ≠1⁡\|λ​\(PΓp\)\|≥γ0,1\-\\max\_\{\\lambda\\neq 1\}\|\\lambda\(P\_\{\\Gamma\_\{p\}\}\)\|\\geq\\gamma\_\{0\},wherePΓpP\_\{\\Gamma\_\{p\}\}is the transition matrix of the random walk onΓp\\Gamma\_\{p\}and the maximum ranges over its eigenvaluesλ≠1\\lambda\\neq 1\.

###### Proof\.

For sufficiently large primespp, the Cayley graphs of𝒢p=SL​\(2,𝔽p\)\\mathcal\{G\}\_\{p\}=\\mathrm\{SL\}\(2,\\mathbb\{F\}\_\{p\}\)with generating set𝕊p\\mathbb\{S\}\_\{p\}form a family of \(combinatorial\) expanders\[Bourgain and Gamburd,[2008](https://arxiv.org/html/2607.27479#bib.bib47)\]\. In other words, there existsp0p\_\{0\}such that for allp≥p0p\\geq p\_\{0\}, there existsγ~\>0\\tilde\{\\gamma\}\>0independent ofppsuch that

λ2​\(PCay​\(𝒢p,𝕊p\)\)≤1−γ~\.\\lambda\_\{2\}\(P\_\{\\mathrm\{Cay\}\(\\mathcal\{G\}\_\{p\},\\mathbb\{S\}\_\{p\}\)\}\)\\leq 1\-\\tilde\{\\gamma\}\.Also note that for odd primes, there are no subgroups of index\-2 ofSL⁡\(2,𝔽p\)\\operatorname\{SL\}\(2,\\mathbb\{F\}\_\{p\}\): any index\-2 subgroup ofSL⁡\(2,𝔽p\)\\operatorname\{SL\}\(2,\\mathbb\{F\}\_\{p\}\)would have to be normal and hence induce a surjective homomorphismφ:SL⁡\(2,𝔽p\)→ℤ/2​ℤ\\varphi:\\operatorname\{SL\}\(2,\\mathbb\{F\}\_\{p\}\)\\to\\mathbb\{Z\}/2\\mathbb\{Z\}\. However,SL⁡\(2,𝔽p\)\\operatorname\{SL\}\(2,\\mathbb\{F\}\_\{p\}\)is generated by the matricesg=\(1a01\)g=\\begin\{pmatrix\}1&a\\\\ 0&1\\end\{pmatrix\}andh=\(10a1\)h=\\begin\{pmatrix\}1&0\\\\ a&1\\end\{pmatrix\}fora∈𝔽pa\\in\\mathbb\{F\}\_\{p\}\. For eacha≠0a\\neq 0,ggandhhhave orderpp, andppis invertible modulo 2, so

φ​\(I\)=φ​\(gp\)=p​φ​\(g\)=0⟹φ​\(g\)=0,\\varphi\(I\)=\\varphi\(g^\{p\}\)=p\\varphi\(g\)=0\\implies\\varphi\(g\)=0,and similarly forφ​\(h\)\\varphi\(h\)\. Henceφ\\varphimust be trivial\. Thus no such index\-2 subgroups can exist\.

Proposition E\.1 inBreuillardet al\.\[[2015](https://arxiv.org/html/2607.27479#bib.bib49)\]states that for a finite groupGG, combinatorially expanding and no index\-2 subgroups implies a two\-sided expansion, i\.e\. there existsγ~0\>0\\tilde\{\\gamma\}\_\{0\}\>0depending on the expander coefficient and number of generatorsk=2k=2such that

maxλ≠1⁡\|λ​\(PCay​\(𝒢p,𝕊p\)\)\|≤1−γ~0\.\\max\_\{\\lambda\\neq 1\}\|\\lambda\(P\_\{\\mathrm\{Cay\}\(\\mathcal\{G\}\_\{p\},\\mathbb\{S\}\_\{p\}\)\}\)\|\\leq 1\-\\tilde\{\\gamma\}\_\{0\}\.Sinceγ~\\tilde\{\\gamma\}does not depend onpp, this bound holds uniformly over the family of Cayley graphs of𝒢p\\mathcal\{G\}\_\{p\}generated by𝕊p\\mathbb\{S\}\_\{p\}forp≥p0p\\geq p\_\{0\}\.

The fact that there are no index\-2 subgroups of the groups𝒢p\\mathcal\{G\}\_\{p\}implies that the \(connected\) Cayley graphsCay​\(𝒢p,𝕊p\)\\mathrm\{Cay\}\(\\mathcal\{G\}\_\{p\},\\mathbb\{S\}\_\{p\}\)are non\-bipartite \(see Lemma 4 in\[van2021bipartite\]\)\. In particular, the eigenvalues of the transition matrices ofPCay​\(𝒢p,𝕊p\)P\_\{\\mathrm\{Cay\}\(\\mathcal\{G\}\_\{p\},\\mathbb\{S\}\_\{p\}\)\}are strictly greater than \-1\. Then for each3≤p<p03\\leq p<p\_\{0\}, there existsγp\>0\\gamma\_\{p\}\>0such that

maxλ≠1⁡\|λ​\(PCay​\(𝒢p,𝕊p\)\)\|≤1−γp\.\\max\_\{\\lambda\\neq 1\}\|\\lambda\(P\_\{\\mathrm\{Cay\}\(\\mathcal\{G\}\_\{p\},\\mathbb\{S\}\_\{p\}\)\}\)\|\\leq 1\-\\gamma\_\{p\}\.Let

γ0=min⁡\{min3≤p<p0⁡γp,γ0~\}\>0\.\\gamma\_\{0\}=\\min\\left\\\{\\min\_\{3\\leq p<p\_\{0\}\}\\gamma\_\{p\},\\tilde\{\\gamma\_\{0\}\}\\right\\\}\>0\.Then the uniform spectral gap holds for all odd primespp\.

Now the spectrum ofPΓpP\_\{\\Gamma\_\{p\}\}corresponding to the Schreier\-coset graph is included in the spectrum ofPCay​\(𝒢p,𝕊p\)P\_\{\\mathrm\{Cay\}\(\\mathcal\{G\}\_\{p\},\\mathbb\{S\}\_\{p\}\)\}corresponding the Cayley graph \(see Proposition 11\.17 and the preceding remark inHooryet al\.\[[2006](https://arxiv.org/html/2607.27479#bib.bib48)\]\), which gives us the claim\.

∎

#### 8\.3\.2Expander Mixing

###### Lemma 8\.2\(Expander Mixing\)\.

For primesp≥3p\\geq 3and allt≥0t\\geq 0, the random walk matrixPΓpP\_\{\\Gamma\_\{p\}\}on a Schreier\-coset graphΓp\\Gamma\_\{p\}with uniform spectral gapγ0\\gamma\_\{0\}satisfies

\|\(PΓpt\)i​v−1\|VΓp\|\|≤\(1−γ0\)t\.\\left\|\(P\_\{\\Gamma\_\{p\}\}^\{t\}\)\_\{iv\}\-\\frac\{1\}\{\|V\_\{\\Gamma\_\{p\}\}\|\}\\right\|\\leq\\left\(1\-\\gamma\_\{0\}\\right\)^\{t\}\.Ift≥log⁡\(2​\|VΓp\|\)γ0t\\geq\\frac\{\\log\(2\|V\_\{\\Gamma\_\{p\}\}\|\)\}\{\\gamma\_\{0\}\}, then\(PΓpt\)i​v≥12​\|VΓp\|\(P\_\{\\Gamma\_\{p\}\}^\{t\}\)\_\{iv\}\\geq\\frac\{1\}\{2\|V\_\{\\Gamma\_\{p\}\}\|\}\.

###### Proof\.

Fix a primep≥3p\\geq 3and letΓ=Γp\\Gamma=\\Gamma\_\{p\}\. LetP=∑kλk​uk​uk⊤P=\\sum\_\{k\}\\lambda\_\{k\}u\_\{k\}u\_\{k\}^\{\\top\}be the spectral decomposition with orthonormal eigenvectorsuku\_\{k\}\. We haveu1=1\|VΓ\|​𝟏u\_\{1\}=\\frac\{1\}\{\\sqrt\{\|V\_\{\\Gamma\}\|\}\}\\mathbf\{1\}withλ1=1\\lambda\_\{1\}=1\. Thus:

Pt=1\|VΓ\|​𝟏𝟏⊤\+∑k=2\|VΓ\|λkt​uk​uk⊤P^\{t\}=\\frac\{1\}\{\|V\_\{\\Gamma\}\|\}\\mathbf\{1\}\\mathbf\{1\}^\{\\top\}\+\\sum\_\{k=2\}^\{\|V\_\{\\Gamma\}\|\}\\lambda\_\{k\}^\{t\}u\_\{k\}u\_\{k\}^\{\\top\}\(1\)Therefore

\(Pt\)i​v=1\|VΓ\|\+∑k=2\|VΓ\|λkt​uk​\(i\)​uk​\(v\)\(P^\{t\}\)\_\{iv\}=\\frac\{1\}\{\|V\_\{\\Gamma\}\|\}\+\\sum\_\{k=2\}^\{\|V\_\{\\Gamma\}\|\}\\lambda\_\{k\}^\{t\}u\_\{k\}\(i\)u\_\{k\}\(v\)\(2\)By Lemma[8\.1](https://arxiv.org/html/2607.27479#S8.Thmtheorem1)we have that\|λk\|≤1−γ0\|\\lambda\_\{k\}\|\\leq 1\-\\gamma\_\{0\}fork≥2k\\geq 2\. Hence, by Cauchy\-Schwarz inequality

\|\(Pt\)i​v−1\|VΓ\|\|\\displaystyle\\left\|\(P^\{t\}\)\_\{iv\}\-\\frac\{1\}\{\|V\_\{\\Gamma\}\|\}\\right\|≤∑k=2\|VΓ\|\|λk\|t​\|uk​\(i\)\|​\|uk​\(v\)\|\\displaystyle\\leq\\sum\_\{k=2\}^\{\|V\_\{\\Gamma\}\|\}\|\\lambda\_\{k\}\|^\{t\}\|u\_\{k\}\(i\)\|\|u\_\{k\}\(v\)\|\(3\)≤\(1−γ0\)t​∑k=2\|VΓ\|\|uk​\(i\)\|​\|uk​\(v\)\|\\displaystyle\\leq\(1\-\\gamma\_\{0\}\)^\{t\}\\sum\_\{k=2\}^\{\|V\_\{\\Gamma\}\|\}\|u\_\{k\}\(i\)\|\|u\_\{k\}\(v\)\|\(4\)≤\(1−γ0\)t​∑k=2\|VΓ\|uk​\(i\)2​∑k=2\|VΓ\|uk​\(v\)2\\displaystyle\\leq\(1\-\\gamma\_\{0\}\)^\{t\}\\sqrt\{\\sum\_\{k=2\}^\{\|V\_\{\\Gamma\}\|\}u\_\{k\}\(i\)^\{2\}\}\\sqrt\{\\sum\_\{k=2\}^\{\|V\_\{\\Gamma\}\|\}u\_\{k\}\(v\)^\{2\}\}\(5\)≤\(1−γ0\)t\\displaystyle\\leq\(1\-\\gamma\_\{0\}\)^\{t\}\(6\)where the last inequality uses∑k=1\|VΓ\|uk​\(i\)2=1\\sum\_\{k=1\}^\{\|V\_\{\\Gamma\}\|\}u\_\{k\}\(i\)^\{2\}=1\(orthonormality\)\. Now note that\(1−γ0\)t≤e−γ0​t\(1\-\\gamma\_\{0\}\)^\{t\}\\leq e^\{\-\\gamma\_\{0\}t\}\. Hence, ift≥log⁡\(2​\|VΓ\|\)γ0t\\geq\\frac\{\\log\(2\|V\_\{\\Gamma\}\|\)\}\{\\gamma\_\{0\}\}, then

\(1−γ0\)t≤e−γ0​t≤12​\|VΓ\|\.\(1\-\\gamma\_\{0\}\)^\{t\}\\leq e^\{\-\\gamma\_\{0\}t\}\\leq\\frac\{1\}\{2\|V\_\{\\Gamma\}\|\}\.It follows that

\(Pt\)i​v≥1\|VΓ\|−12​\|VΓ\|=12​\|VΓ\|\.\(P^\{t\}\)\_\{iv\}\\geq\\frac\{1\}\{\|V\_\{\\Gamma\}\|\}\-\\frac\{1\}\{2\|V\_\{\\Gamma\}\|\}=\\frac\{1\}\{2\|V\_\{\\Gamma\}\|\}\.∎

#### 8\.3\.3Effective Resistance

###### Lemma 8\.3\(Effective Resistance Bound\)\.

For any primep≥3p\\geq 3and verticesu,v∈VΓu,v\\in V\_\{\\Gamma\},

ReffΓp​\(u,v\)≤2d​γ0,R\_\{\\mathrm\{eff\}\}^\{\\Gamma\_\{p\}\}\(u,v\)\\leq\\frac\{2\}\{d\\gamma\_\{0\}\},whered=\|𝕊\|d=\|\\mathbb\{S\}\|is the degree andγ0\\gamma\_\{0\}is the uniform spectral gap\.

###### Proof\.

For add\-regular graphΓ\\Gammawith transition matrixPPhaving spectral gapγ\\gamma, Lemma 2\.2, Property 3 inCaiet al\.\[[2023](https://arxiv.org/html/2607.27479#bib.bib44)\]gives us that

12​\(1d​\(u\)\+1d​\(v\)\)≤Reff​\(u,v\)≤1λ2​\(L~\)⋅\(1d​\(u\)\+1d​\(v\)\)\\frac\{1\}\{2\}\\Big\(\\frac\{1\}\{d\(u\)\}\+\\frac\{1\}\{d\(v\)\}\\Big\)\\leq R\_\{\\mathrm\{eff\}\}\(u,v\)\\leq\\frac\{1\}\{\\lambda\_\{2\}\(\\tilde\{L\}\)\}\\cdot\\Big\(\\frac\{1\}\{d\(u\)\}\+\\frac\{1\}\{d\(v\)\}\\Big\)\(7\)where,L~\\tilde\{L\}is the normalized Laplacian ofΓ\\Gamma\. Therefore, we haved​\(u\)=d​\(v\)=dd\(u\)=d\(v\)=dfor all verticesu,v∈Vu,v\\in V\. Therefore:

1d≤Reff​\(u,v\)≤2d⋅λ2​\(L~\)\\frac\{1\}\{d\}\\leq R\_\{\\mathrm\{eff\}\}\(u,v\)\\leq\\frac\{2\}\{d\\cdot\\lambda\_\{2\}\(\\tilde\{L\}\)\}\(8\)Now, for add\-regular graph, the normalized Laplacian isL~=I−P\\tilde\{L\}=I\-P, wherePPis a transition matrix\. Therefore, ifλ\\lambdais an eigenvalue ofPP, then1−λ1\-\\lambdais an eigenvalue ofL~\\tilde\{L\}\. Specifically:

- •λ1=1−λ1​\(P\)=1−1=0\\lambda\_\{1\}=1\-\\lambda\_\{1\}\(P\)=1\-1=0
- •λ2​\(L~\)=1−λ2​\(P\)\\lambda\_\{2\}\(\\tilde\{L\}\)=1\-\\lambda\_\{2\}\(P\)

Now, applying the spectral gap condition,

λ2​\(L~\)=1−λ2​\(P\)≥1−\(1−γ\)=γ\\lambda\_\{2\}\(\\tilde\{L\}\)=1\-\\lambda\_\{2\}\(P\)\\geq 1\-\(1\-\\gamma\)=\\gamma\(9\)Substituting this lower bound to the inequality in \([8](https://arxiv.org/html/2607.27479#S8.E8)\), we get:

ReffΓ​\(u,v\)≤2d⋅λ2​\(L~\)≤2d​γ\.R\_\{\\mathrm\{eff\}\}^\{\\Gamma\}\(u,v\)\\leq\\frac\{2\}\{d\\cdot\\lambda\_\{2\}\(\\tilde\{L\}\)\}\\leq\\frac\{2\}\{d\\gamma\}\.\(10\)This bound is tight up to constants, as the effective resistance can indeed approach this upper bound for pairs of vertices that are apart in the graph structure\., particularly in expander graphs where the spectral gapγ\\gammais bounded away from zero\. Now takeγ=γ0\\gamma=\\gamma\_\{0\}as our uniform spectral gap so that this holds for all primesp≥3p\\geq 3\. ∎

#### 8\.3\.4Spectral Mapping Construction

LetGin=\(Vin,Ein\)G\_\{\\mathrm\{in\}\}=\(V\_\{\\mathrm\{in\}\},E\_\{\\mathrm\{in\}\}\)be the input graph\. We construct a locality\-preserving mapϕ:Vin→VΓ\\phi:V\_\{\\mathrm\{in\}\}\\to V\_\{\\Gamma\}\(withϕ​\(v\)=gv​H\\phi\(v\)=g\_\{v\}H\) as follows: Case \(i\)\|Vin\|≤\|VΓ\|\|V\_\{\\mathrm\{in\}\}\|\\leq\|V\_\{\\Gamma\}\|: LetLin,LΓL\_\{\\mathrm\{in\}\},L\_\{\\Gamma\}be \(normalized\) Laplacians with eigenvectors\{ψi\},\{φi\}\\\{\\psi\_\{i\}\\\},\\\{\\varphi\_\{i\}\\\}ordered by eigenvalues\. DefineΦin​\(v\)=\(ψ2​\(v\),…,ψr\+1​\(v\)\)\\Phi\_\{\\mathrm\{in\}\}\(v\)=\(\\psi\_\{2\}\(v\),\\ldots,\\psi\_\{r\+1\}\(v\)\)andΦΓ​\(x\)=\(φ2​\(x\),…,φr\+1​\(x\)\)∈ℝr\\Phi\_\{\\Gamma\}\(x\)=\(\\varphi\_\{2\}\(x\),\\ldots,\\varphi\_\{r\+1\}\(x\)\)\\in\\mathbb\{R\}^\{r\}\. Setϕ\\phiby solving:

minϕ:Vin↪VΓ​∑\(u,v\)∈EindistΓ​\(ϕ​\(u\),ϕ​\(v\)\)such that‖ΦΓ​\(ϕ​\(v\)\)−Φin​\(v\)‖2≤ε∀v\.\\min\_\{\\phi:V\_\{\\mathrm\{in\}\}\\hookrightarrow V\_\{\\Gamma\}\}\\ \\sum\_\{\(u,v\)\\in E\_\{\\mathrm\{in\}\}\}\\mathrm\{dist\}\_\{\\Gamma\}\(\\phi\(u\),\\phi\(v\)\)\\quad\\text\{such that\}\\quad\\\|\\Phi\_\{\\Gamma\}\(\\phi\(v\)\)\-\\Phi\_\{\\mathrm\{in\}\}\(v\)\\\|\_\{2\}\\leq\\varepsilon\\ \\ \\forall v\.\(11\)Case \(ii\)\|Vin\|\>\|VΓ\|\|V\_\{\\mathrm\{in\}\}\|\>\|V\_\{\\Gamma\}\|: Use disjoint copiesΓ\(1\),…,Γ\(q\)\\Gamma^\{\(1\)\},\\ldots,\\Gamma^\{\(q\)\}\(orΓ×Kq\\Gamma\\times K\_\{q\}\) and apply \(i\) per block\.

###### Theorem 8\.4\(Locality Control\)\.

Assume there exists constantscin<∞c\_\{\\mathrm\{in\}\}<\\inftyandcΓ\>0c\_\{\\Gamma\}\>0such thatΦin\\Phi\_\{\\mathrm\{in\}\}andΦΓ\\Phi\_\{\\Gamma\}satisfy

‖Φin​\(u\)−Φin​\(v\)‖2≤cin​distin⁡\(u,v\)\\\|\\Phi\_\{\\mathrm\{in\}\}\(u\)\-\\Phi\_\{\\mathrm\{in\}\}\(v\)\\\|\_\{2\}\\leq c\_\{\\mathrm\{in\}\}\\operatorname\{dist\}\_\{\\mathrm\{in\}\}\(u,v\)for everyu,v∈Vinu,v\\in V\_\{\\mathrm\{in\}\}and

‖ΦΓ​\(x\)−ΦΓ​\(y\)‖2≥cΓ​distΓ⁡\(x,y\)\\\|\\Phi\_\{\\Gamma\}\(x\)\-\\Phi\_\{\\Gamma\}\(y\)\\\|\_\{2\}\\geq c\_\{\\Gamma\}\\operatorname\{dist\}\_\{\\Gamma\}\(x,y\)for everyx,y∈ϕ​\(Vin\)x,y\\in\\phi\(V\_\{\\mathrm\{in\}\}\)\. If‖ΦΓ​\(ϕ​\(v\)\)−Φin​\(v\)‖2≤ϵ\\\|\\Phi\_\{\\Gamma\}\(\\phi\(v\)\)\-\\Phi\_\{\\mathrm\{in\}\}\(v\)\\\|\_\{2\}\\leq\\epsilonfor everyvv, then

distΓ⁡\(ϕ​\(u\),ϕ​\(v\)\)≤cincΓ​distin⁡\(u,v\)\+2​ϵcΓ\.\\operatorname\{dist\}\_\{\\Gamma\}\(\\phi\(u\),\\phi\(v\)\)\\leq\\frac\{c\_\{\\mathrm\{in\}\}\}\{c\_\{\\Gamma\}\}\\operatorname\{dist\}\_\{\\mathrm\{in\}\}\(u,v\)\+\\frac\{2\\epsilon\}\{c\_\{\\Gamma\}\}\.

###### Proof\.

By assumption, there exists constantscin<∞c\_\{\\mathrm\{in\}\}<\\inftyandcΓ\>0c\_\{\\Gamma\}\>0such thatΦin\\Phi\_\{\\mathrm\{in\}\}andΦΓ\\Phi\_\{\\Gamma\}satisfy

‖Φin​\(u\)−Φin​\(v\)‖2≤cin​distin⁡\(u,v\)\\\|\\Phi\_\{\\mathrm\{in\}\}\(u\)\-\\Phi\_\{\\mathrm\{in\}\}\(v\)\\\|\_\{2\}\\leq c\_\{\\mathrm\{in\}\}\\operatorname\{dist\}\_\{\\mathrm\{in\}\}\(u,v\)for everyu,v∈Vinu,v\\in V\_\{\\mathrm\{in\}\}and

‖ΦΓ​\(x\)−ΦΓ​\(y\)‖2≥cΓ​distΓ⁡\(x,y\)\\\|\\Phi\_\{\\Gamma\}\(x\)\-\\Phi\_\{\\Gamma\}\(y\)\\\|\_\{2\}\\geq c\_\{\\Gamma\}\\operatorname\{dist\}\_\{\\Gamma\}\(x,y\)for everyx,y∈ϕ​\(Vin\)x,y\\in\\phi\(V\_\{\\mathrm\{in\}\}\)\. Since‖ΦΓ​\(ϕ​\(v\)\)−Φin​\(v\)‖2≤ϵ\\\|\\Phi\_\{\\Gamma\}\(\\phi\(v\)\)\-\\Phi\_\{\\mathrm\{in\}\}\(v\)\\\|\_\{2\}\\leq\\epsilon, we have by the triangle inequality that

‖ΦΓ​\(ϕ​\(u\)\)−ΦΓ​\(ϕ​\(v\)\)‖2\\displaystyle\\\|\\Phi\_\{\\Gamma\}\(\\phi\(u\)\)\-\\Phi\_\{\\Gamma\}\(\\phi\(v\)\)\\\|\_\{2\}≤‖Φin​\(u\)−Φin​\(v\)‖2\+2​ϵ\\displaystyle\\leq\\\|\\Phi\_\{\\mathrm\{in\}\}\(u\)\-\\Phi\_\{\\mathrm\{in\}\}\(v\)\\\|\_\{2\}\+2\\epsilon≤cin​distin⁡\(u,v\)\+2​ϵ\.\\displaystyle\\leq c\_\{\\mathrm\{in\}\}\\operatorname\{dist\}\_\{\\mathrm\{in\}\}\(u,v\)\+2\\epsilon\.Thus

distΓ⁡\(ϕ​\(u\),ϕ​\(v\)\)\\displaystyle\\operatorname\{dist\}\_\{\\Gamma\}\(\\phi\(u\),\\phi\(v\)\)≤1cΓ​‖ΦΓ​\(ϕ​\(u\)\)−ΦΓ​\(ϕ​\(v\)\)‖2\\displaystyle\\leq\\frac\{1\}\{c\_\{\\Gamma\}\}\\\|\\Phi\_\{\\Gamma\}\(\\phi\(u\)\)\-\\Phi\_\{\\Gamma\}\(\\phi\(v\)\)\\\|\_\{2\}≤cincΓ​distin⁡\(u,v\)\+2​ϵcΓ\.\\displaystyle\\leq\\frac\{c\_\{\\mathrm\{in\}\}\}\{c\_\{\\Gamma\}\}\\operatorname\{dist\}\_\{\\mathrm\{in\}\}\(u,v\)\+\\frac\{2\\epsilon\}\{c\_\{\\Gamma\}\}\.∎

#### 8\.3\.5Effective Resistance Analysis of Rewired Graph

Augmented SystemThe augmented system couplesGinG\_\{\\mathrm\{in\}\}withΓ\\Gammavia edges\{\(v,ϕ​\(v\)\)\}\\\{\(v,\\phi\(v\)\)\\\}of conductanceε\>0\\varepsilon\>0\. All edges inEinE\_\{\\mathrm\{in\}\}andEΓE\_\{\\Gamma\}have unit conductance\. LetP∈\{0,1\}\|Vin\|×\|VΓ\|P\\in\\\{0,1\\\}^\{\|V\_\{\\mathrm\{in\}\}\|\\times\|V\_\{\\Gamma\}\|\}be the injection/matching matrix withPv,ϕ​\(v\)=1P\_\{v,\\phi\(v\)\}=1and0otherwise\. Then the augmented Laplacian is

Laug=\[Lin\+ε​I−ε​P−ε​P⊤LΓ\+ε​P⊤​P\]\.L\_\{\\mathrm\{aug\}\}=\\begin\{bmatrix\}L\_\{\\mathrm\{in\}\}\+\\varepsilon I&\-\\varepsilon P\\\\ \-\\varepsilon P^\{\\top\}&L\_\{\\Gamma\}\+\\varepsilon P^\{\\top\}P\\end\{bmatrix\}\.\(12\)
###### Theorem 8\.5\(Effective Resistance in Rewired Graph\)\.

In the rewired graphGrwdG^\{\\mathrm\{rwd\}\}, the effective resistance between nodesu,v∈Vinu,v\\in V\_\{\\mathrm\{in\}\}satisfies

Reffrwd​\(u,v\)≤min⁡\{Reffin​\(u,v\),ReffΓ​\(ϕ​\(u\),ϕ​\(v\)\)\+2ε\}\.R\_\{\\mathrm\{eff\}\}^\{\\mathrm\{rwd\}\}\(u,v\)\\leq\\min\\Big\\\{R\_\{\\mathrm\{eff\}\}^\{\\mathrm\{in\}\}\(u,v\),\\;R\_\{\\mathrm\{eff\}\}^\{\\Gamma\}\(\\phi\(u\),\\phi\(v\)\)\+\\frac\{2\}\{\\varepsilon\}\\Big\\\}\.

###### Proof\.

We prove this using:Rayleigh–Thomson PrincipleEffective resistance equals the minimum energy of a unitu→vu\\\!\\to\\\!vflow\. Consider two feasible unit flows:

*Route 1:*Use the minimum\-energy unit flow inGinG\_\{\\mathrm\{in\}\}only\. This has energyReffin​\(u,v\)R\_\{\\mathrm\{eff\}\}^\{\\mathrm\{in\}\}\(u,v\), henceReffrwd​\(u,v\)≤Reffin​\(u,v\)R\_\{\\mathrm\{eff\}\}^\{\\mathrm\{rwd\}\}\(u,v\)\\leq R\_\{\\mathrm\{eff\}\}^\{\\mathrm\{in\}\}\(u,v\)\.

*Route 2:*Send one unit across the coupling edge\(u,ϕ​\(u\)\)\(u,\\phi\(u\)\), then route throughΓ\\Gammafromϕ​\(u\)\\phi\(u\)toϕ​\(v\)\\phi\(v\)using the minimum\-energy unit flow inΓ\\Gamma, then send one unit across\(v,ϕ​\(v\)\)\(v,\\phi\(v\)\)\. Coupling edges have conductanceε\\varepsilonand thus resistance1/ε1/\\varepsilon, so each coupling edge contributes energy1/ε1/\\varepsilon\(unit flow\)\. TheΓ\\Gammasegment contributesReffΓ​\(ϕ​\(u\),ϕ​\(v\)\)R\_\{\\mathrm\{eff\}\}^\{\\Gamma\}\(\\phi\(u\),\\phi\(v\)\)sinceΓ\\Gammaedges have unit conductance\. Therefore this route has total energy

ReffΓ​\(ϕ​\(u\),ϕ​\(v\)\)\+2ε\.R\_\{\\mathrm\{eff\}\}^\{\\Gamma\}\(\\phi\(u\),\\phi\(v\)\)\+\\frac\{2\}\{\\varepsilon\}\.Taking the minimum over all flows yields

Reffrwd​\(u,v\)≤min⁡\{Reffin​\(u,v\),ReffΓ​\(ϕ​\(u\),ϕ​\(v\)\)\+2ε\}\.R\_\{\\mathrm\{eff\}\}^\{\\mathrm\{rwd\}\}\(u,v\)\\leq\\min\\Big\\\{R\_\{\\mathrm\{eff\}\}^\{\\mathrm\{in\}\}\(u,v\),\\;R\_\{\\mathrm\{eff\}\}^\{\\Gamma\}\(\\phi\(u\),\\phi\(v\)\)\+\\frac\{2\}\{\\varepsilon\}\\Big\\\}\.∎

###### Theorem 8\.6\(Over\-Squashing Mitigation\)\.

For anyu,v∈Vinu,v\\in V\_\{\\mathrm\{in\}\}withu≠vu\\neq v,

ρ​\(u,v\):=Reffin​\(u,v\)Reffrwd​\(u,v\)≥max⁡\{1,Reffin​\(u,v\)ReffΓ​\(ϕ​\(u\),ϕ​\(v\)\)\+2ε\}\.\\rho\(u,v\):=\\frac\{R\_\{\\mathrm\{eff\}\}^\{\\mathrm\{in\}\}\(u,v\)\}\{R\_\{\\mathrm\{eff\}\}^\{\\mathrm\{rwd\}\}\(u,v\)\}\\geq\\max\\left\\\{1,\\;\\frac\{R\_\{\\mathrm\{eff\}\}^\{\\mathrm\{in\}\}\(u,v\)\}\{R\_\{\\mathrm\{eff\}\}^\{\\Gamma\}\(\\phi\(u\),\\phi\(v\)\)\+\\frac\{2\}\{\\varepsilon\}\}\\right\\\}\.

###### Proof\.

LetR=Reffin​\(u,v\)R=R\_\{\\mathrm\{eff\}\}^\{\\mathrm\{in\}\}\(u,v\)andB=ReffΓ​\(ϕ​\(u\),ϕ​\(v\)\)\+2εB=R\_\{\\mathrm\{eff\}\}^\{\\Gamma\}\(\\phi\(u\),\\phi\(v\)\)\+\\frac\{2\}\{\\varepsilon\}\. From Theorem[8\.5](https://arxiv.org/html/2607.27479#S8.Thmtheorem5), we have that

1Reffrwd​\(u,v\)≥max⁡\{1R,1B\}\.\\frac\{1\}\{R\_\{\\mathrm\{eff\}\}^\{\\mathrm\{rwd\}\}\(u,v\)\}\\geq\\max\\left\\\{\\frac\{1\}\{R\},\\frac\{1\}\{B\}\\right\\\}\.Hence, sinceR≥0R\\geq 0,

ρ​\(u,v\)\\displaystyle\\rho\(u,v\)=RReffrwd​\(u,v\)\\displaystyle=\\frac\{R\}\{R\_\{\\mathrm\{eff\}\}^\{\\mathrm\{rwd\}\}\(u,v\)\}≥max⁡\{RR,RB\}\\displaystyle\\geq\\max\\left\\\{\\frac\{R\}\{R\},\\frac\{R\}\{B\}\\right\\\}=max⁡\{1,Reffin​\(u,v\)ReffΓ​\(ϕ​\(u\),ϕ​\(v\)\)\+2ε\}\.\\displaystyle=\\max\\left\\\{1,\\frac\{R\_\{\\mathrm\{eff\}\}^\{\\mathrm\{in\}\}\(u,v\)\}\{R\_\{\\mathrm\{eff\}\}^\{\\Gamma\}\(\\phi\(u\),\\phi\(v\)\)\+\\frac\{2\}\{\\varepsilon\}\}\\right\\\}\.
∎

##### Remark A\.3\.1

For pairs with largeReffin​\(u,v\)R\_\{\\mathrm\{eff\}\}^\{\\mathrm\{in\}\}\(u,v\), the ratioReffrwd​\(u,v\)/Reffin​\(u,v\)R\_\{\\mathrm\{eff\}\}^\{\\mathrm\{rwd\}\}\(u,v\)/R\_\{\\mathrm\{eff\}\}^\{\\mathrm\{in\}\}\(u,v\)decays asO​\(1/Reffin​\(u,v\)\)O\(1/R\_\{\\mathrm\{eff\}\}^\{\\mathrm\{in\}\}\(u,v\)\), and becomes small wheneverReffin​\(u,v\)≫2d​γ\+2εR\_\{\\mathrm\{eff\}\}^\{\\mathrm\{in\}\}\(u,v\)\\gg\\frac\{2\}\{d\\gamma\}\+\\frac\{2\}\{\\varepsilon\}\.

#### 8\.3\.6Performance Guarantees

###### Theorem 8\.7\(Performance Guarantees\)\.

Suppose the transition matrices of random walks on the Schreier\-coset graphs satisfy

1−λ2​\(PΓp\)≥γ0\>01\-\\lambda\_\{2\}\(P\_\{\\Gamma\_\{p\}\}\)\\geq\\gamma\_\{0\}\>0uniformly inppand defineB0=2d​γ0\+2ϵB\_\{0\}=\\frac\{2\}\{d\\gamma\_\{0\}\}\+\\frac\{2\}\{\\epsilon\}\. Then for everyu,v∈Vinu,v\\in V\_\{\\mathrm\{in\}\}withu≠vu\\neq v,

Reffrwd​\(u,v\)≤Reffin​\(u,v\)​B0Reffin​\(u,v\)\+B0\.R\_\{\\mathrm\{eff\}\}^\{\\mathrm\{rwd\}\}\(u,v\)\\leq\\frac\{R\_\{\\mathrm\{eff\}\}^\{\\mathrm\{in\}\}\(u,v\)B\_\{0\}\}\{R\_\{\\mathrm\{eff\}\}^\{\\mathrm\{in\}\}\(u,v\)\+B\_\{0\}\}\.Consequently,

ρ​\(u,v\)≥1\+Reffin​\(u,v\)B0\.\\rho\(u,v\)\\geq 1\+\\frac\{R\_\{\\mathrm\{eff\}\}^\{\\mathrm\{in\}\}\(u,v\)\}\{B\_\{0\}\}\.

###### Proof\.

LetR=Reffin​\(u,v\)R=R\_\{\\mathrm\{eff\}\}^\{\\mathrm\{in\}\}\(u,v\)and the resistance of the Schreier\-coset graph by pass with conductanceε\\varepsilonbyB=ReffΓp​\(ϕ​\(u\),ϕ​\(v\)\)\+2εB=R\_\{\\mathrm\{eff\}\}^\{\\Gamma\_\{p\}\}\(\\phi\(u\),\\phi\(v\)\)\+\\frac\{2\}\{\\varepsilon\}\. By Lemma[8\.3](https://arxiv.org/html/2607.27479#S8.Thmtheorem3), we have thatReffΓp≤2d​γ0R\_\{\\mathrm\{eff\}\}^\{\\Gamma\_\{p\}\}\\leq\\frac\{2\}\{d\\gamma\_\{0\}\}, and so

B≤2d​γ0\+2ε=B0\.B\\leq\\frac\{2\}\{d\\gamma\_\{0\}\}\+\\frac\{2\}\{\\varepsilon\}=B\_\{0\}\.Now choose an optimal unit flowfinf\_\{\\mathrm\{in\}\}fromu→vu\\to vsupported onGinG\_\{\\mathrm\{in\}\}with energyRRand a unit flowfΓf\_\{\\Gamma\}fromu→vu\\to vthat travels through the coupling edges andΓp\\Gamma\_\{p\}with energyBB\. Leta∈\[0,1\]a\\in\[0,1\]be the fraction of the current going through the input layer and1−a1\-athrough the Schreier graph:

fa=a⋅fin\+\(1−a\)​fΓ\.f\_\{a\}=a\\cdot f\_\{\\mathrm\{in\}\}\+\(1\-a\)f\_\{\\Gamma\}\.This is another unit flow fromu→vu\\to vwith disjoint edge supports, so its energy is

E​\(fa\)=a2​R\+\(1−a\)2​B\.E\(f\_\{a\}\)=a^\{2\}R\+\(1\-a\)^\{2\}B\.The energy is minimized when

so

a∗=BR\+B,1−a∗=RR\+Ba\_\{\*\}=\\frac\{B\}\{R\+B\},\\quad 1\-a\_\{\*\}=\\frac\{R\}\{R\+B\}with

E​\(fa∗\)=R​BR\+B\.E\(f\_\{a\_\{\*\}\}\)=\\frac\{RB\}\{R\+B\}\.As the functionx↦R​xR\+xx\\mapsto\\frac\{Rx\}\{R\+x\}is increasing forx\>0x\>0andB≤B0B\\leq B\_\{0\}, we have that

Reffrwd​\(u,v\)≤R​B0R\+B0=Reffin​\(u,v\)​B0Reffin​\(u,v\)\+B0\.R\_\{\\mathrm\{eff\}\}^\{\\mathrm\{rwd\}\}\(u,v\)\\leq\\frac\{RB\_\{0\}\}\{R\+B\_\{0\}\}=\\frac\{R\_\{\\mathrm\{eff\}\}^\{\\mathrm\{in\}\}\(u,v\)B\_\{0\}\}\{R\_\{\\mathrm\{eff\}\}^\{\\mathrm\{in\}\}\(u,v\)\+B\_\{0\}\}\.For the second claim,

ρ​\(u,v\)\\displaystyle\\rho\(u,v\)=Reffin​\(u,v\)Reffrwd​\(u,v\)≥RR​B0/\(R\+B0\)=R\+B0B0=1\+RB0=1\+Reffin​\(u,v\)B0\.\\displaystyle=\\frac\{R\_\{\\mathrm\{eff\}\}^\{\\mathrm\{in\}\}\(u,v\)\}\{R\_\{\\mathrm\{eff\}\}^\{\\mathrm\{rwd\}\}\(u,v\)\}\\geq\\frac\{R\}\{RB\_\{0\}/\(R\+B\_\{0\}\)\}=\\frac\{R\+B\_\{0\}\}\{B\_\{0\}\}=1\+\\frac\{R\}\{B\_\{0\}\}=1\+\\frac\{R\_\{\\mathrm\{eff\}\}^\{\\mathrm\{in\}\}\(u,v\)\}\{B\_\{0\}\}\.
∎

### 8\.4Algorithm Functions

The following functions are sub\-functions ofAlgorithm 1

#### 8\.4\.1FindN

The\(modn\)\\pmod\{n\}for the groupS​L​\(2,ℤn\)SL\(2,\\mathbb\{Z\}\_\{n\}\)is selected based on input graph size\. The algorithm searches for smallestni​nn\_\{in\}such that the resulting Schreier\-Coset size\|VΓ\|\|V\_\{\\Gamma\}\|satisfies\|VΓ\|≥ni​n\|V\_\{\\Gamma\}\|\\geq n\_\{in\}\. This ensures complete coverage of input nodes\. To optimize expansion properties, asmallest primestrategy is applied to prioritize prime moduli\. The results are cached to ensure the search and subsequent graph construction occur only once per unique graph size\. This helps in dynamic scaling as it encompases the entire graph nodes, expands optimally by leveraging theS​L​\(2,ℤn\)SL\(2,\\mathbb\{Z\}\_\{n\}\)properties providing high\-conductivity bypasses\.

Algorithm 2Automatic Modulo Selection \(FindN\)Input node count

ninn\_\{\\mathrm\{in\}\}, search strategy

SS
Modulo

nnand coset\-space size

\|VΓ\|\|V\_\{\\Gamma\}\|
if

\(nin,S\)\(n\_\{\\mathrm\{in\}\},S\)is cachedthen

returncached values

endif

for

ncand←2n\_\{\\mathrm\{cand\}\}\\leftarrow 2to

max⁡\(100,nin\+10\)\\max\(100,n\_\{\\mathrm\{in\}\}\+10\)do

size←EstimateSize​\(ncand\)\\mathrm\{size\}\\leftarrow\\textsc\{EstimateSize\}\(n\_\{\\mathrm\{cand\}\}\)
if

size≥nin\\mathrm\{size\}\\geq n\_\{\\mathrm\{in\}\}then

if

S=’prime’∧IsPrime​\(ncand\)S=\\text\{'prime'\}\\land\\textsc\{IsPrime\}\(n\_\{\\mathrm\{cand\}\}\)then

breakwith

\(ncand,size\)\(n\_\{\\mathrm\{cand\}\},\\mathrm\{size\}\)
endif

if

S=’smallest’S=\\text\{'smallest'\}then

breakwith

\(ncand,size\)\(n\_\{\\mathrm\{cand\}\},\\mathrm\{size\}\)
endif

endif

endfor

Fallback:returnthe cached result for

n=5n=5if no candidate is found\.

#### 8\.4\.2FiedlerRanking

To establish the spectral mapping, we compute the Fiedler ranking of the nodes in both the input graphGi​nG\_\{in\}and the auxiliary Schreier graphΓ\\Gamma\. We utilize an iterative power method to approximate the eigenvector corresponding to second smallest eigenvalue of the normalized Laplacian\. Starting from a random vector orthogonalized against the trivial eigenvector𝟏\\mathbf\{1\}, we repeatedly apply the symmetric normalized adjacency operator and re\-orthogonalize to ensure convergence\. The resulting vector is a one\-dimensional embedding that reflects the global connectivity and "bottleneck" structure of the graph\. Nodes are then ranked by their values in this vector to determine the pairing for the constant\-degree SCGR overlay

Algorithm 3Spectral Node Ranking \(FiedlerRanking\)Graph

GG, number of nodes

nn, iterations

TT
Sorted node indices \(ranks\)

Ls​y​m←L\_\{sym\}\\leftarrowcompute symmetric normalized adjacency matrix

D−1/2​A​D−1/2D^\{\-1/2\}AD^\{\-1/2\}
v1←degreesv\_\{1\}\\leftarrow\\sqrt\{\\text\{degrees\}\}⊳\\trianglerightTrivial eigenvector component

v←Random vector∈ℝnv\\leftarrow\\text\{Random vector \}\\in\\mathbb\{R\}^\{n\}
v←v−projv1​\(v\)v\\leftarrow v\-\\text\{proj\}\_\{v\_\{1\}\}\(v\)⊳\\trianglerightEnsure orthogonality to trivial eigenvector

for

t←1t\\leftarrow 1to

TTdo

v←Ls​y​m​vv\\leftarrow L\_\{sym\}v
v←v−projv1​\(v\)v\\leftarrow v\-\\text\{proj\}\_\{v\_\{1\}\}\(v\)⊳\\trianglerightRe\-orthogonalize

v←v/‖v‖v\\leftarrow v/\\\|v\\\|⊳\\trianglerightNormalize

endfor

return

Argsort​\(v\)\\textsc\{Argsort\}\(v\)

#### 8\.4\.3LiftFeatures

The Lift Features function establishes initial hidden states for auxiliary Schrier nodes\. As the mappingϕ\\phimay be many\-to\-one depending on the ratio\|VΓ\|\)\(ni​n\\frac\{\|V\_\{\\Gamma\}\|\)\}\{\(n\_\{in\}\}, the feature of the each auxiliary node is computed using the mean node embedding of all input nodes mapped to that specific coset\. The average acts as a feature pool, ensuring communication layer is initialized with representation of the original graph\.

Algorithm 4Feature Lifting \(LiftFeatures\)Input features

Xin∈ℝni​n×dX\_\{\\mathrm\{in\}\}\\in\\mathbb\{R\}^\{n\_\{in\}\\times d\}, Spectral mapping

ϕ\\phi, Coset count

\|VΓ\|\|V\_\{\\Gamma\}\|
Auxiliary features

XΓ∈ℝ\|VΓ\|×dX\_\{\\Gamma\}\\in\\mathbb\{R\}^\{\|V\_\{\\Gamma\}\|\\times d\}
XΓ←𝟎\|VΓ\|×dX\_\{\\Gamma\}\\leftarrow\\mathbf\{0\}^\{\|V\_\{\\Gamma\}\|\\times d\}⊳\\trianglerightInitialize auxiliary feature matrix

C←𝟎\|VΓ\|×1C\\leftarrow\\mathbf\{0\}^\{\|V\_\{\\Gamma\}\|\\times 1\}⊳\\trianglerightInitialize node counts for averaging

for

i←1i\\leftarrow 1to

ni​nn\_\{in\}do

v←ϕ​\(i\)v\\leftarrow\\phi\(i\)⊳\\trianglerightFind the target coset node

XΓ​\[v\]←XΓ​\[v\]\+Xin​\[i\]X\_\{\\Gamma\}\[v\]\\leftarrow X\_\{\\Gamma\}\[v\]\+X\_\{\\mathrm\{in\}\}\[i\]⊳\\trianglerightAggregate features

C​\[v\]←C​\[v\]\+1C\[v\]\\leftarrow C\[v\]\+1⊳\\trianglerightIncrement occupancy count

endfor

XΓ←XΓ/max⁡\(C,1\)X\_\{\\Gamma\}\\leftarrow X\_\{\\Gamma\}/\\max\(C,1\)⊳\\trianglerightNormalize by averaging features

return

XΓX\_\{\\Gamma\}

#### 8\.4\.4SchreierTransform

The SchreierTransform function is implemented as a whole method, encompassing group modulusnnsuch that the resulting coset is at least as large as the input graph ensuring full coverage, fiedler ranking for bothGi​nG\_\{in\}andΓ\\Gammawhich aligns nodes based on their global connectivity profiles\.

The final augmented graph is constructed by concatenating the original edges with the 4\-regular Schreier edges and bi\-directional coupling edges that link original nodes to their spectrally aligned counterparts in the coset space\. Node features in auxiliary nodes are initialized by lifting and averaging the input featuresXi​nX\_\{in\}through the mappingϕ\\phi\.

The construction introduces highly connected bypasses that effectively reduce the graph’s effective resistance \(ER\), facilitating long\-range communication and mitigating over\-squashing in bottleneck heavy grap structures\.

Algorithm 5Schreier\-Coset Graph Rewiring \(SCGR\)Input graph

Gi​n​\(V,E,X\)G\_\{in\}\(V,E,X\), coupling strength

ϵ\\epsilon, mapping booleanspectral

Augmented graph

Ga​u​g​\(V′,E′,X′\)G^\{aug\}\(V^\{\\prime\},E^\{\\prime\},X^\{\\prime\}\)
n←FindN​\(\|V\|,strategy\)n\\leftarrow\\textsc\{FindN\}\(\|V\|,\\text\{strategy\}\)⊳\\trianglerightSelect optimal group modulus

Γ​\(VΓ,EΓ\)←BuildSchreierGraph​\(n\)\\Gamma\(V\_\{\\Gamma\},E\_\{\\Gamma\}\)\\leftarrow\\textsc\{BuildSchreierGraph\}\(n\)⊳\\trianglerightConstruct expander overlay

ifspectralthen

ϕ←SpectralAlign​\(Gi​n,Γ\)\\phi\\leftarrow\\textsc\{SpectralAlign\}\(G\_\{in\},\\Gamma\)⊳\\trianglerightPair nodes via Fiedler rankings

else

ϕ\(u\)←u\(mod\|VΓ\|\)∀u∈V\\phi\(u\)\\leftarrow u\\pmod\{\|V\_\{\\Gamma\}\|\}\\quad\\forall u\\in V⊳\\trianglerightUniform fallback mapping

endif

XΓ←AverageFeatures​\(X,ϕ\)X\_\{\\Gamma\}\\leftarrow\\textsc\{AverageFeatures\}\(X,\\phi\)⊳\\trianglerightInitialize auxiliary node features

Ec​p​l←\{\(u,ϕ​\(u\)\+\|V\|\),\(ϕ​\(u\)\+\|V\|,u\)∣u∈V\}E\_\{cpl\}\\leftarrow\\\{\(u,\\phi\(u\)\+\|V\|\),\(\\phi\(u\)\+\|V\|,u\)\\mid u\\in V\\\}⊳\\trianglerightDefine coupling edges

return

Gi​n∪Γ∪Ec​p​lG\_\{in\}\\cup\\Gamma\\cup E\_\{cpl\}with weight

ϵ\\epsilonfor

Ec​p​lE\_\{cpl\}

### 8\.5Experiments

#### 8\.5\.1Hyperparameters

We initialize the SCGR\-augmented GNNs using acoupling\_strengthofϵ=1\.0\\epsilon=1\.0and perform spectral alignment with 100 Fiedler iterations\. The auxiliary group modulusnnis selected dynamically via asmallest\_primestrategy, and all models are trained using the Adam optimizer with a consistent learning rate and weight decay\.

#### 8\.5\.2Effective Resistance: Benchmark Datasets

Table[3](https://arxiv.org/html/2607.27479#S8.T3)represents the ER values for the benchmark datasets\.SCGRon every dataset attains lower Effective Resistance illustrating better connectivity across graph nodes\.

Table 3:Effective resistance on benchmark datasets\. Percentages in parentheses indicate the reduction in effective resistance relative to the corresponding baseline model\.SCGR reduces effective resistance across all benchmark configurations\. The reductions range from approximately 5% to 71%, with reductions of 15% or more in eight of the ten model–dataset configurations\. The improvement is comparatively modest on PROTEINS, where SCGR reduces effective resistance by 6\.4% for GCN and 4\.9% for GIN due to its relatively simple graph topology and less severe connectivity bottlenecks\.

The percentage reduction in effective resistance is computed relative to the corresponding baseline model\. Specifically,ER​baseline\\mathrm\{ER\}\{\\text\{baseline\}\}denotes the effective resistance obtained using the original GCN or GIN architecture, whileER​SCGR\\mathrm\{ER\}\{\\text\{SCGR\}\}denotes the value obtained after incorporating SCGR\. A positive percentage therefore indicates that SCGR lowers effective resistance, with a larger percentage representing a greater improvement in graph connectivity\.

ER Reduction\(%\)=ERbaseline−ERSCGRERbaseline×100\.\\text\{ER Reduction\}~\(\\%\)=\\frac\{\\mathrm\{ER\}\_\{\\text\{baseline\}\}\-\\mathrm\{ER\}\_\{\\text\{SCGR\}\}\}\{\\mathrm\{ER\}\_\{\\text\{baseline\}\}\}\\times 100\.\(13\)

#### 8\.5\.3Effective Resistance: Stochastic Block Models

We evaluateSCGRusing Stochastic Block Models \(SBM\) withn=1,000n=1,000nodes andK=50K=50communities\. By generating synthetic graphs with 1,000 nodes partitioned into 50 communities, we systematically vary the internal and external edge probabilities to simulate a wide range of graph modularitiespi​n:0\.1−0\.4p\_\{in\}:0\.1\-0\.4andpo​u​t:10−3−10−1\.5p\_\{out\}:10^\{\-3\}\-10^\{\-1\.5\}to simulate diverse modularity regimes\. Each 2\-layer GCN uses 64\-dimensional random features, ReLU activation, and Adam optimizationl​r=0\.01lr=0\.01, weight decay=5×10−4=5\\times 10^\{\-4\}over 80 epochs\.SCGRaugmentation employs a d = 4 Schreier expander, coupling strengthϵ=1\.0\\epsilon=1\.0, and 100\-iteration Fiedler mapping\. This controlled setup isolates topological bottlenecks, demonstrating that SCGR’s hierarchical bypasses consistently reduce effective resistance and recover accuracy\.

We evaluate the structural impact of our expander overlay by computing the average Effective Resistance \(ER\) using the pseudo\-inverse of the graph Laplacian, further validating the results through a Schur complement projection of the augmented Laplacian\.

The results, as shown in theTable[4](https://arxiv.org/html/2607.27479#S8.T4)andFigure[4](https://arxiv.org/html/2607.27479#S8.F4)reveal that SCGR consistently provides alternative low\-resistance pathways—bounded theoretically by2/\(d​γ\)2/\(d\\gamma\)\. This defines significant accuracy gains in low\-modularity regimes where the GCN baseline is otherwise severely limited by structural bottlenecks\.

Table 4:GCN accuracy and effective resistance \(ER\) on SBM graphs\.![Refer to caption](https://arxiv.org/html/2607.27479v1/Figures/ERM.png)Figure 4:Comparison of effective resistance across different SBM modularities\.
#### 8\.5\.4OGBG \- Molhiv, OGBG \- Molpcba

For, molecular prediction task,SCGRis assessed on theOpen Graph Benchmark \- Graph PredictionOgbg\-MolhivandOgbg\-MolpcbadatasetsHuet al\.\[[2020](https://arxiv.org/html/2607.27479#bib.bib43)\]\. The experimental protocol adheres to the implementation and hyperparameter configuration specified byHuet al\.\[[2020](https://arxiv.org/html/2607.27479#bib.bib43)\]withlayers: 5, hidden dimension: 300, a dropout: 0\.5, and a batch size :64

SCGRexhibits robust predictive performance while maintaining high structural fidelity\. Schreier\-coset in both configurations attains highest ROC\-AUC score in Molhiv dataset\. For the Molpcba dataset,GCN\+SCGRattains the highest average precision, withGIN\+SCGRremaining competitive based on the inherent scale and structural complexity of Molpcba\. For GIN on Molpcba, the standard deviation of 0\.0767 likely reflects instability in the Fiedler mapping at Molpcba scale, where fixed\-budget power iteration may not yield a reliable structural embedding across runs\.

Table 5:Performance comparison on OGBG\-MOLHIV and OGBG\-MOLPCBA\.
#### 8\.5\.5LRGB \- Peptides Struct\. Peptides Func

ThePeptides\-Struct and Peptides\-Funcdatasets, sourced from theLong Range Graph Benchmarksuite provides challenging molecular property prediction tasks that necessitate modeling long\-range dependencies in graph structures\.Peptides\-Func\(Classification\), is evaluated using Average Precision \(AP\)\.Peptides\-Struct\(Regression\) predicts functional properties of peptides, measured by the mean absolute error \(MAE\)\.

Table 6:Performance comparison on PEPTIDES\-FUNC \(Test AP↑\\uparrow\) and PEPTIDES\-STRUCT \(Test MAE↓\\downarrow\)Table[6](https://arxiv.org/html/2607.27479#S8.T6)demonstrates SCGR accomplished highest scores in both parameters across both peptide prediction tasks\. Schreier Coset delivered a substantial improvement over the strongest baseline, with particularly notable gains when combined with GIN:\+13\.4%:\+13\.4\\%onPeptides\-Funcand a−9\.2%\-9\.2\\%error reduction onPeptides\-Struct\. Even with GCN,SCGRoutperforms all competing rewiring methods\. These consistent improvements across both architectures and tasks validate its effectiveness in enabling GNNs to capture the long\-range molecular interactions critical for accurate peptide property prediction, where traditional message passing approaches struggle due to limited receptive fields over\-squashing bottlenecks\.

### 8\.6Ablation Studies

#### 8\.6\.1Node Classification

We evaluate the performance ofS​L​\(2,ℤn\)SL\(2,\\mathbb\{Z\}\_\{n\}\)against a random 4\-regular baseline to test the necessity of algebraic symmetry\. To isolate the impact of spectral alignment, we contrast Fiedler\-based mapping with random node permutations\. Finally, we conduct a sensitivity analysis on the coupling strengthϵ∈\[0\.1,2\.0\]\\epsilon\\in\[0\.1,2\.0\]\.These are performed on Amazon Computers and Amazon Photo\.

Results on both Amazon Computers and Amazon Photo yield significant improvements in accuracies\. The "Random 4\-regular" augmentation consistently performs the worst across both datasets, emphasizing that expansion alone is insufficient\. The peak performance atϵ=1\.0\\epsilon=1\.0suggests that for certain node\-level tasks, the SCGR provides critical contextual information that local neighborhoods alone cannot capture\.

Table 7:Ablation for Node Classification benchmark
#### 8\.6\.2Graph Classification

Using the same ablation metrics, we perform tests on Mutag, Enzymes, Proteins, Collab, Imdb domains to ensure the robustness of SCGR design\.

The analysis depicts that SCGRϵ=1\.0\\epsilon=1\.0consistently optimizes the bottleneck\-performance trade\-off\. On COLLAB, we achieve a massive\+8\.8%\+8\.8\\%accuracy boost and a71\.1%71\.1\\%reduction in effective resistance\. Across all datasets, the Random Map version frequently degrades accuracy, proving that spectral alignment is vital for useful signal propagation\. While Random 4\-regular expansion often yields lower absolute resistance, it consistently performs poorly in accuracy\. Our findings demonstrate thatϵ=1\.0\\epsilon=1\.0, group theoreticS​L​\(2,ℤn\)SL\(2,\\mathbb\{Z\}\_\{n\}\)provide the ideal balance for global communication without washing out essential local properties\.

Table 8:Ablation Study for Graph Classification BenchmarkMUTAGENZYMESPROTEINSCOLLABIMDB\-BConfigurationAcc\.ReffR\_\{\\text\{eff\}\}Acc\.ReffR\_\{\\text\{eff\}\}Acc\.ReffR\_\{\\text\{eff\}\}Acc\.ReffR\_\{\\text\{eff\}\}Acc\.ReffR\_\{\\text\{eff\}\}GCN \(Baseline\)73\.1601556253\.7501047569\.2001317168\.8005758\.763\.40020220\+ Random 4\-reg72\.630720151\.1706120\.869\.2007200\.069\.8002161\.458\.80010098\+ SCGR \(Random Map\)71\.8401575153\.9201122669\.4201488771\.0002822\.258\.10012959\+ SCGR \(ϵ=0\.1\\epsilon=0\.1\)75\.2601470352\.4208709\.868\.2601534074\.4003086\.760\.75015472\+ SCGR \(ϵ=0\.5\\epsilon=0\.5\)75\.5301379851\.9208837\.270\.8001577271\.6002657\.262\.05013321\+ SCGR \(ϵ=1\.0\\epsilon=1\.0\)77\.8901003553\.8308845\.0772\.5901233277\.6001664\.061\.60013091\+ SCGR \(ϵ=2\.0\\epsilon=2\.0\)73\.4201501549\.4201058168\.6601403472\.4004453\.657\.30013027