1. 论文介绍

论文题目：Mitigating Over-Squashing in Graph Neural Networks by Spectrum-Preserving Sparsification
论文领域：图神经网络，图重连算法
论文发表：ICML 2025
论文代码：https://github.com/Jinx-byebye/GOKU.git
论文背景：

2. 论文摘要

图神经网络的消息传递范式通常由于某些图区域中的结构瓶颈而难以在远程节点之间交换信息，这种限制称为过度挤压。为了减少这种瓶颈，图重布线（graph rewring）作为一种改进图拓扑结构的方法得到了广泛的应用。然而，现有的图重布线技术往往忽略了保持原始图的关键特性的需要，例如，谱特性。此外，许多方法依赖于增加边缘计数来改善连通性，这引入了大量计算开销并加剧了过度平滑的风险。本文提出了一种新的图重布线方法，该方法利用图的谱保持和稀疏化来减少过度挤压。该方法在保持稀疏性的同时生成连通性增强的图，并在很大程度上保留了原始图谱，有效地平衡了结构瓶颈减少和图属性保持。实验结果验证了该方法的有效性，表明其在分类精度和保留拉普拉斯谱方面优于强基线方法。

3. 相关介绍

本文贡献
1，提出了一种新的稠密化-稀疏化的图重连算法DSR来缓解过度挤压问题，DSR是第一个图重连算法同时满足（1）保持连通性以有效的消息传递，（2）实现图稀疏化以计算高效，（3）明确地保留了图谱，以保证结构的保真度。
2，提出了一种新算法GOKU，这是所提出的DSR算法的一个实用且有效的实例。
3，实验证明了GOKU算法的有效性

PANDA提出了替代性消息传递机制，专注于扩展宽度感知的消息传递。
已有的这些方法改善了连通性，但它们往往从根本上改变了拓扑结构，忽视了保持图结构的重要意义。
"图谱"，在图论中指的是图的拉普拉斯矩阵特征值集合。对于图分类，属于同一类的图往往比来自不同类的图具有更相似的特征值分布。
对于节点分类，来自同一类别的节点在基于特征向量的特征表示中表现出更高的平均余弦相似度，而不同类别的节点则表现较低（使用前128个特征向量的组件，每个节点生成一个128维的特征向量）。

谱稀疏化：
谱稀疏化指的是产生一个来源于原始图的稀疏化图，其拉普拉斯矩阵在原始图的拉普拉斯矩阵近似。

图谱相似图的定义

其中有定义$x^TLx=\sum_{(u,v)\in E}w_{uv}(x_u-x_v)^2$ ，

图谱稀疏化的定义

4. DSR算法

DSR算法包含两个序列模块，图的密集化和图的稀疏化。

DSR算法的整体架构为

对于稀疏化会删除重要的边从而降低整个图的连通性。使用USS算法（unimportantance-based spectral sparsification）的反过程来实现图的稀疏化。
USS算法伪代码

所以使用ISS算法（importance-based spectral sparsification）来进行稀疏化图。
ISS算法的伪代码

相比当前的其他算法，ISS算法通过谱稀疏化的同时保留了图谱；算法集成了密集化和稀疏化，保证最终的稀疏图不超过原始图的密集度；不同于其他决定性的边定义方式，本算法是基于概率性的修改边策略；最后，通过利用图谱的特性，添加边的数量是从一个成熟的理论结果推导出来的，而不是一个启发式选择的值。

图的密集化问题可以定义为最大似然估计问题。

5. GOKU算法

全称是（Graph rewiring to tackle Over-squashing by Keeping graph spectra throUgh spectral sparsification）（通过光谱稀疏化保持图谱以解决过度压缩问题的图重连算法）

当使用USS算法，计算边的重要程度是根据

其中fu和fv是费德勒向量Fiedler vector的分量（与第二小特征值相关的特征向量
为什么上面公式的值越大表示边的不重要程度越大：从直观看，分母|fu - fv|越大，意味着u和v之间的关联越小。小的度数说明了节点与其他节点的关系微弱。

根据反稀疏化来求解最大似然估计
选择候选边作为图密集化的操作，选择2i个有着最大的绝对Fiedler值的节点和2j个有着最小度的节点。这些节点群的节点对之间的边一般有着最小的边的值。然后随机从中选择其中的一定数量的边添加到图中。

图稀疏化
采用基于有效阻尼的稀疏化方法。

6. 实验设置

对于节点分类任务，采用数据集有Cora，Citeseer，Texas，Cornell，Wisconsin 和 Chameleon，其中包括异质图和同质图。
对于图级分类任务，使用数据集有Enzymes，Imdb，Mutag，Proteins

基础模型采用多种，有GCN，GIN 和 GCNII

实验结果
基于GCN的各个图重连算法的比较

基于GIN的比较

图谱的可视化
GOKU算法可以最好的保持了图谱的值

消融实验
很简单的把GOKU算法分别去掉稀疏层和密集层来进行实验

有效阻尼的分析
GOKU算法明显的降低了整个图的有效阻尼.

7. 核心Python代码

def goku(edge_list, features, num_relations=2, mini_k=10, method='kts', epsilon=0.1, step_size=0.1, device='cuda:0',
         to_undirected=True, metric='degree', beta=1.0):
    """
    Graph Optimization through Kombinatorial Unification (GOKU) rewiring algorithm.
    
    This method combines graph densification (latent graph recovery) with sparsification to 
    create a computational graph structure that preserves key properties of the original graph
    while improving message passing capabilities for GNN architectures.
    
    Args:
        edge_list (numpy.ndarray): Original edge list of shape (E, 2).
        features (torch.Tensor): Node feature matrix of shape (num_nodes, feature_dim).
        num_relations (int): Number of relation types to use in the computational graph.
        mini_k (int): Initial guess for the number of edges to add during densification.
        method (str): Method for effective resistance calculation ('ext', 'spl', 'kts').
        epsilon (float): Accuracy parameter for effective resistance calculation.
        step_size (float): Step size for increasing epsilon during latent graph recovery.
        device (str): Device to use for calculations ('cpu' or 'cuda:0').
        to_undirected (bool): Whether to convert the sampled graph to an undirected graph.
        metric (str): Method for selecting edges to add ('degree' or other).
        beta (float): Scaling factor for sparsification calculations.
        
    Returns:
        tuple: (computational_edge_index, edge_type, computational_edge_weight)
            - computational_edge_index: Tensor of shape (2, E') representing rewired edges
            - edge_type: Tensor of shape (E',) representing edge types
            - computational_edge_weight: Tensor of shape (E',) representing edge weights
    """
    num_nodes = features.shape[0]
    edge_index = torch.tensor(edge_list.T, dtype=torch.long).to(device)  # Convert to tensor of shape (2, E)
    original_edge_count = edge_index.shape[1]

    # Step 1: Apply graph densification to recover latent graph structure
    latent_edge_index = recover_latent_graph(
        edge_index, 
        num_nodes, 
        mini_k,
        step_size, 
        metric
    )
    latent_edge_count = latent_edge_index.size(1)

    # Create uniform edge weights, scaled to maintain the original average weight
    edge_weight = torch.ones_like(latent_edge_index[0]).cpu() * original_edge_count / latent_edge_count

    # Step 2: Apply graph sparsification to create the computational graph
    computational_edge_index, edge_type, computational_edge_weight = sparsification(
        edge_index,  # Original edges
        latent_edge_index.cpu().numpy().transpose(),  # Latent edges
        edge_weight,  # Uniform weights
        features,  # Node features
        num_samples=original_edge_count,  # Target number of edges in computational graph
        method=method,  
        epsilon=epsilon,
        undirected=to_undirected,
        num_relations=num_relations,
        beta=beta
    )

    return computational_edge_index, edge_type, computational_edge_weight

8. 总结

GOKU算法在实验中明显提升了图的同质，且对图的社区结构的边有保留.
GOKU算法对节点对之间的有效电阻显著降低。 这种减少表明，在重新连接的图中，局部和全局连通性都有所改善.

9. 个人感悟

整个文章有点类似是各个基础方法的大拼盘，在整体的结构上缺乏一个清晰的证明。其次是超参数较多，对这种实验向的结果比较有较大的抵触动机。