Schreier-Coset Graph Rewiring

# Schreier 陪集图重连

来源：https://arxiv.org/html/2607.27479  
Randy Martinez¹、Lizhen Lin（[email protected]）

###### 摘要

图神经网络（GNN）中的信息流从根本上受到过挤压（over-squashing）的限制，即结构瓶颈会阻碍长距离信息传播。图重连方法通过修改图拓扑来缓解这一问题，并已被广泛使用。然而，现有方法往往会引入高昂的结构与计算瓶颈，无法保留原始图的关键性质，并且会大幅增加边数。我们提出了一种新方法——**Schreier–陪集图重连（Schreier-Coset Graph Rewiring, SCGR）**，这是一种基于群论的重连方法，它利用从特殊线性群导出的 Schreier 陪集图对输入图进行增广。我们的方法提供了理论保证，得到的图具有谱间隙和有界有效电阻，为长距离通信构建了低电阻旁路。实验评估表明，SCGR 在各种学习任务上将有效电阻降低了 55–40%，在有效缓解连通性瓶颈的同时保持了具有竞争力的准确率。

## 1 引言与相关工作

图是通过连接链路（边）将实体（节点）与其他实体连接起来的网络结构，用于表示关系（Harary (1969)[https://arxiv.org/html/2607.27479#bib.bib1]；Diestel (2012)[https://arxiv.org/html/2607.27479#bib.bib2]；Shuman 等 (2013)[https://arxiv.org/html/2607.27479#bib.bib3]；Hamilton 等 (2017a)[https://arxiv.org/html/2607.27479#bib.bib4]）。图能够捕捉关系信息和结构信息，这使它们在生物学、拓扑学、推荐系统以及连通结构信息等众多领域中极具价值（Battaglia 等 (2018)[https://arxiv.org/html/2607.27479#bib.bib5]；Sanchez-Gonzalez 等 (2018)[https://arxiv.org/html/2607.27479#bib.bib6]；Gilmer 等 (2017)[https://arxiv.org/html/2607.27479#bib.bib7]；Berg 等 (2017)[https://arxiv.org/html/2607.27479#bib.bib9]；Koh 等 (2024)[https://arxiv.org/html/2607.27479#bib.bib8]）。图神经网络（GNN）是为处理图结构数据而专门开发的一类神经网络。GNN 通常采用消息传递范式（He 等 (2023)[https://arxiv.org/html/2607.27479#bib.bib13]），节点通过迭代交换并聚合来自邻居的信息来更新节点表示（Jiang 等 (2019)[https://arxiv.org/html/2607.27479#bib.bib10]；Kipf (2017)[https://arxiv.org/html/2607.27479#bib.bib11]；Veličković 等 (2017)[https://arxiv.org/html/2607.27479#bib.bib12]）。为了捕捉图内的长距离信息或交互，通常需要深层 GNN 架构。然而，增加层数往往会引入结构和计算瓶颈。尤其会导致来自大规模邻域的大量信息被压缩到固定大小的嵌入中，即所谓的过挤压（Alon 和 Yahav (2021)[https://arxiv.org/html/2607.27479#bib.bib14]；Arnaiz-Rodriguez 和 Errica (2025)[https://arxiv.org/html/2607.27479#bib.bib24]）。过挤压限制了 GNN 捕捉长距离依赖的能力，从而降低了需要全局上下文的任务性能。

已有多种方法被用于解决 GNN 中的过挤压问题。在**特征增强（Feature Augmentation）**中，节点/边属性会与全局信号一起得到丰富。Eliasof 等 (2023)[https://arxiv.org/html/2607.27479#bib.bib35] 将前 \(k\) 个拉普拉斯特征向量拼接至每个节点，从而无需逐跳传播长距离信息。然而，特征分解的计算成本为 \(O(n^3)\)，内存成本为 \(O(nk)\)，并且批次效率低下。

**图重连（Graph Rewiring）**通过 *a)* 添加节点或 *b)* 重新配置边来修改输入（原始）图，从而生成增强节点间连通性的输出图。例如，Deac 等 (2022)[https://arxiv.org/html/2607.27479#bib.bib15] 构造了扩展图。Wilson 等 (2024)[https://arxiv.org/html/2607.27479#bib.bib16] 使用 Cayley 图来辅助信息传播。另一些工作则利用曲率（Fesser 和 Weber (2024)[https://arxiv.org/html/2607.27479#bib.bib17]）、谱扩展（Karhadkar 等 (2023)[https://arxiv.org/html/2607.27479#bib.bib18]）和有效电阻（Black 等 (2023)[https://arxiv.org/html/2607.27479#bib.bib19]）等性质来修改拓扑以优化信息流。

现有的图重连技术有两个局限：*a)* 过度改变输入图的边；*b)* 引入更多新边。扩展图重连方法会引入全新的节点集合，与输入图的结构差异很大（rampášek 2023）。图变换器依赖全连接神经网络（FCNN），计算规模呈二次增长。Delaunay 图（Attali 等，2024[https://arxiv.org/html/2607.27479#bib.bib20]）具有图直径减小和有效电阻更低等优点。然而，它仅根据节点特征构造图，完全忽略了原始图的拓扑结构。

> 图 1：展示了 Schreier–陪集图重连框架。原始图的局部性得以保留，\(d\)-正则图 \(\Gamma\) 提供具有有界有效电阻的常度数捷径，并通过菲德勒排序（Fiedler Ranking）对齐节点（OSQ 表示过挤压的边连接）。

在重连过程中保留图的局部性至关重要，因为许多学习任务（如图上的聚类和半监督学习）依赖于输入图的谱性质来保证准确结果。这些方法通常会引入大量附加边来增强连通性，这既增加了在重连输出图上进行学习的计算成本（Arnaiz-Rodriguez 和 Errica (2025)[https://arxiv.org/html/2607.27479#bib.bib24]），也增加了过平滑的风险（Li 等 (2018)[https://arxiv.org/html/2607.27479#bib.bib21]；Liang 等 (2023a)[https://arxiv.org/html/2607.27479#bib.bib22], b[https://arxiv.org/html/2607.27479#bib.bib23]）。

为了解决过挤压问题，我们提出了 **Schreier–陪集图重连（SCGR）**（方法流程示意见图 1[https://arxiv.org/html/2607.27479#S1.F1]），这是一种基于群论的方法，利用由特殊线性群 \(\mathrm{SL}(2,\mathbb{Z}_n)\) 的陪集构造的 **Schreier 陪集图**。

##### 主要贡献

我们的主要贡献总结如下：

- **Schreier–陪集（SCGR）形式化**：我们定义了 Schreier 陪集图的新构造，并将其应用于 GNN 的重连增广中。顶点对应于 \(\mathrm{SL}(2,\mathbb{Z}_n)\) 模一个上三角子群的陪集，常数生成元集产生一个 \(d\)-正则图。
- **理论分析**：我们通过定义并推导节点-陪集映射、谱性质、增广图上的有效电阻界以及过挤压缓解保证，为 SCGR 提供了强有力的理论保证。
- **实证评估**：我们在节点分类和图分类基准上评估了 SCGR，并通过改变 SBM（随机块模型）图的模块度来测试准确率和有效电阻界。我们的大量数值结果表明，SCGR 与重连基线方法相比持续持平或取得更高分数。

### 1.1 相关工作与局限性

大多数缓解过挤压的方法都是通过重连来修改输入图。基于扩展图的重连方法（Deac 等 (2022)[https://arxiv.org/html/2607.27479#bib.bib15]）利用 Cayley 图保持较小的直径，但其节点集表示可能与输入图不同。Black 等 (2023)[https://arxiv.org/html/2607.27479#bib.bib19] 通过最小化有效电阻来减少瓶颈。Attali 等 (2024)[https://arxiv.org/html/2607.27479#bib.bib20] 基于节点特征构造新图，忽略了原始图的谱性质。FoSR（Karhadkar 等 (2023)[https://arxiv.org/html/2607.27479#bib.bib18]）通过添加边来改进谱间隙的一阶近似。基于曲率的方法已通过依据几何原理添加和删除边来增强连通性（Topping 等 (2021)[https://arxiv.org/html/2607.27479#bib.bib34]；Nguyen 等 (2023)[https://arxiv.org/html/2607.27479#bib.bib31]）。ProxyGap（Jamadandi 等 (2024)[https://arxiv.org/html/2607.27479#bib.bib36]）基于 Braess (1968)[https://arxiv.org/html/2607.27479#bib.bib37] 的方法来修改边。Qian 等 (2024)[https://arxiv.org/html/2607.27479#bib.bib38] 探索了概率方法。PANDA（Choi 等，2024[https://arxiv.org/html/2607.27479#bib.bib39]）提出了基于宽度的替代消息传递机制。Finkelshtein 等 (2024)[https://arxiv.org/html/2607.27479#bib.bib40] 在消息传递范式中引入了一种可学习的协作机制。这些方法确实改善了连通性，但它们激进地改变了拓扑，忽略了原始图的谱性质。

## 2 面向 GNN 的 Schreier–陪集重连

### 2.1 图预备知识

**图（Graph）**。设 \(G=(V,E)\) 表示一个无向、连通且非二分图，其中节点集为 \(V\)，边集为 \(E\)，其邻接矩阵为 \(A\in\mathbb{R}^{n_{\mathrm{in}}\times n_{\mathrm{in}}}\)，若 \((i,j)\in E\) 则 \(A_{ij}=1\)，否则为 0，其中 \(|V|=n_{\mathrm{in}}\)。对角度数矩阵为 \(D=\mathrm{diag}(d_1,\dots,d_n)\)，其中 \(D_{vv}=d_v\)。归一化拉普拉斯矩阵为 \(L=D^{-1/2}(D-A)D^{-1/2}\)。\(L\) 的特征值满足 \(0=\lambda_0\le\lambda_1\le\cdots\le\lambda_{n_{\mathrm{in}}-1}\)。与 \(\lambda_1\) 关联的特征向量提供了反映图连通性的节点规范一维嵌入。

**特殊线性群 \(\mathrm{SL}(2,\mathbb{Z}_n)\)**。设 \(\mathbb{Z}_n=\mathbb{Z}/n\mathbb{Z}\) 表示模 \(n\) 的整数环。群 \(\mathcal{G}=\mathrm{SL}(2,\mathbb{Z}_n)\) 定义为：
\[
\mathcal{G}=\mathrm{SL}(2,\mathbb{Z}_n)=\left\{M\in\mathbb{Z}_n^{2\times 2}\mid \det(M)\equiv 1\pmod{n}\right\},
\]
其中 \(n\) 取决于输入图的大小。注意，这里的 \(n\) 与输入图大小 \(n_{\mathrm{in}}\) 不同。我们选择满足足够 Schreier–陪集覆盖的最小素数 \(n\)。

**子群（Subgroup）**。设 \(H\subset \mathrm{SL}(2,\mathbb{Z}_n)\) 是 \(\mathcal{G}\) 中由单位行列式对角矩阵构成的子群：
\[
H=\left\{\begin{pmatrix}a&0\\0&d\end{pmatrix}\in\mathcal{G}\mid ad\equiv 1\pmod{n}\right\}.
\]

**生成元集（Generator）**。设 \(\mathbb{S}\) 为生成元集：
\[
\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）**。扩展图是稀疏但高度连通的图。我们使用基于特殊线性群 \(\mathrm{SL}(2,\mathbb{Z}_n)\) 及生成元集 \(\mathbb{S}\) 的 Cayley 图 \(\mathrm{Cay}(\mathcal{G};\mathbb{S})\) 的预计算扩展图。虽然这些图具有良好的扩展性质，但实现较大的节点数通常不现实，因为
\[
\|V(\mathrm{Cay}(\mathcal{G};\mathbb{S}))\|=n^3\prod_{\text{prime }p\mid n}\left(1-\frac{1}{p^2}\right),
\]
这会在 \(n\) 较大时产生过高的内存需求（\(n\) 需满足 \(\|V(\mathrm{Cay}(\mathcal{G};\mathbb{S}))\|\) 的要求）。

## 3 Schreier 陪集图 \(\Gamma\)

Schreier 陪集图提供了有限生成群在 \(\mathrm{SL}(2,\mathbb{Z}_n)\) 的某个子群之陪集上的置换表示。SC 图在我们的方法中起着关键作用，它作为一个辅助结构，通过群论对称性编码了鲁棒的扩展与混合行为。形式上，对于群 \(\mathcal{G}\)、子群 \(H\subseteq\mathcal{G}\)、生成元集 \(\mathbb{S}\subseteq\mathcal{G}\)，Schreier 陪集图 \(\Gamma=(V_\Gamma,E_\Gamma)\) 定义为：

- **顶点集**：\(V_\Gamma=\left\{gH:g\in\mathcal{G}\right\}\)（所有左陪集的集合）。
- **边集**：对于每个 \(gH\in V_\Gamma\) 和每个 \(s\in\mathbb{S}\)，将无向边 \(gH\) 与 \((sg)H\) 加入 \(E_\Gamma\)。

由于每个陪集对每个生成元都有一个邻居，因此产生一个 \(d\)-正则图，其中 \(d=|\mathbb{S}|\)。

在构造 Schreier 图时，我们采用*典范构造*。也就是说，\(\Gamma\) 是在群 \(\mathcal{G}=\mathrm{SL}(2,\mathbb{Z}_n)\) 上构造的，子群 \(H\) 由对角矩阵组成，并使用初等行变换作为生成元：
\[
\mathbb{S}=\left\{\begin{pmatrix}1&\pm 1\\0&1\end{pmatrix},\begin{pmatrix}1&0\\\pm 1&1\end{pmatrix}\right\}\bmod n.
\]
所得的 Schreier 陪集图具有
\[
\|V_\Gamma\|=|\mathrm{SL}(2,\mathbb{Z}_n)|/\|H\|=n(n^2-1)/\varphi(n)
\]
个顶点，其中 \(\varphi(n)\) 是欧拉函数。

### 3.1 Schreier 引导的图重连

我们按照算法 1[https://arxiv.org/html/2607.27479#alg1] 中的方式，使用由 Schreier 陪集图 \(\Gamma\) 引导的保结构重连来增广输入图 \(G_{\mathrm{in}}=(V_{\mathrm{in}},E_{\mathrm{in}})\)。该方法的核心是一个保局部性映射 \(\phi:V_{\mathrm{in}}\to V_\Gamma\)。

##### 谱映射构造

设 \(L_{\mathrm{in}},L_\Gamma\) 为归一化拉普拉斯矩阵，其特征向量分别为 \(\psi_i,\varphi_{\mathrm{in}}\)。我们定义
\[
\Phi_{\mathrm{in}}(v)=(\psi_2(v),\ldots,\psi_{r+1}(v))
\]
以及
\[
\Phi_\Gamma(x)=(\varphi_2(x),\ldots,\varphi_{r+1}(x))\in\mathbb{R}^r
\]
我们通过下式选择 \(\phi\)：
\[
\min_{\phi}\ \sum_{(u,v)\in E_{\mathrm{in}}}\mathrm{dist}_\Gamma(\phi(u),\phi(v))
\]
满足
\[
\|\Phi_\Gamma(\phi(v))-\Phi_{\mathrm{in}}(v)\|_2\le\varepsilon\quad \forall v.
\]
若 \(|V_{\mathrm{in}}|>|V_\Gamma|\)，则使用 \(q=\lceil|V_{\mathrm{in}}|/|V_\Gamma|\rceil\) 个不相交的 \(\Gamma\) 副本或 \(\Gamma\times K_q\)，并对每个副本应用上述过程。

**算法 1** Schreier–陪集变换：图重连方法（第 3.1 节）

输入：输入图 \(G_{\mathrm{in}}=(V_{\mathrm{in}},E_{\mathrm{in}})\)，特征 \(X_{\mathrm{in}}\)；耦合强度 \(\epsilon>0\)；选择策略 \(S\)；布尔值 spectral_map  
输出：增广图 \(G^{\mathrm{rwd}} = (V^{\mathrm{rwd}},E^{\mathrm{rwd}},X^{\mathrm{rwd}},w^{\mathrm{rwd}})\)

```
n ← FindN(|V_in|, S)
Γ ← SchreierTransform(n)，Γ = (V_Γ, E_Γ)
if spectral_map then
    Φ_in ← G_in
    Φ_Γ ← Γ
    φ ← FiedlerRanking(V_in, V_Γ, Φ_in, Φ_Γ)
else
    φ(u) ← 1 + ((idx(u)−1) mod |V_Γ|)  ∀u ∈ V_in
```