摘要

图神经网络（Graph Neural Networks, GNNs）在多种领域中已展现出与现有方法相媲美的性能，能够有效应对各类图相关任务，包括节点分类、图分类、链接预测以及节点和图聚类等。大多数GNN基于消息传递（message passing）框架，因此也被称为消息传递神经网络（MPNNs）。尽管取得了令人瞩目的成果，MPNNs仍被广泛报道存在过平滑（over-smoothing）、过压缩（over-squashing）和欠传播（under-reaching）等问题。为缓解这些局限性，学术界提出了图重连（graph rewiring）与图池化（graph pooling）等方法。然而，当前多数先进的图重连方法在保留图的全局拓扑结构方面表现不佳，且通常不具备可微性或归纳性，同时需要手动调参。本文提出一种名为DiffWire的新颖图重连框架，专为MPNN设计，其核心思想基于Lovász界（Lovász bound），具备原理严谨、完全可微且无需参数的特性。该方法通过引入两种新型、互补的MPNN层，构建了统一的图重连理论体系：CT-Layer（Commute Time Layer）能够学习节点间的通行时间（commute time），并将其作为边权重调整的相关性函数；GAP-Layer（Spectral Gap Optimization Layer）则根据网络特性和具体任务需求，优化图的谱间隙（spectral gap）。我们通过基准图分类数据集，分别实证验证了这两种层的有效性。此外，还开展了初步研究，探讨CT-Layer在同质性（homophilic）与异质性（heterophilic）节点分类任务中的适用性。DiffWire将通行时间的学习与曲率相关定义相结合，为构建更具表达能力的MPNN开辟了新路径。