分层多尺度图神经网络：通过缓解过平滑和过挤压实现可扩展的异配学习

# 补充项目 来源：https://arxiv.org/html/2605.10975 ###### 摘要 在从社交网络到分子相互作用的现实世界应用中，异配性（heterophily，即相邻节点携带不同标签）图十分普遍。然而，现有的针对异配性图分类的光谱图神经网络（GNN）方法受到中心节点主导（节点度较大）的聚合和过平滑问题的困扰，因为其次优的多项式滤波器引入了近似误差并混合了远距离信号。为了解决这种受度偏差影响的聚合和次优的多项式滤波问题，我们引入了层次多视图 Haar（HMH），这是一种新颖的光谱图学习框架，具有近线性的扩展性。HMH 首先通过异配性感知的编码器学习特征和结构感知的*有符号*亲和力，然后根据这些嵌入构建一个软图层次结构。在每个层次级别，HMH 构建一个稀疏、正交且具有局部感知能力的 Haar 基，以便在频域中应用可学习的光谱滤波器。最后，跳跃连接的上采样层将所有层次级别的输出组合回原始图，从而有效防止中心节点主导和长距离信号瓶颈（过挤压）。实验表明，HMH 优于最先进的光谱基线模型，在节点分类数据集上实现了高达 3% 的提升，在图分类数据集上实现了 7 个百分点的提升，同时保持了线性扩展能力。图神经网络，异配性，小波，粗化，过挤压 ## 1 引言 现实世界中的图很少是均匀的：某些区域相对同质，邻近节点共享相似的特征和连接性；而其他区域则是异配性的，其中邻居在属性和结构上都有显著差异。在图学习中，同质区域通常受益于平滑/平均（低通滤波），而异配区域则需要对比度放大（高通滤波）\(Chien et al., 2021 (https://arxiv.org/html/2605.10975#bib.bib5)\)。光谱图神经网络（GNNs）旨在通过将信号投影到图拉普拉斯算子的全局特征基或其多项式近似上来捕捉此类信号\(Zhu & Koniusz, 2021 (https://arxiv.org/html/2605.10975#bib.bib39)\)。使用全局基，无论是显式预计算\(He et al., 2022 (https://arxiv.org/html/2605.10975#bib.bib15)\)还是使用高阶多项式隐式近似\(Huang et al., 2024 (https://arxiv.org/html/2605.10975#bib.bib17)\)，往往会牺牲图的局部性。由此产生的滤波器可以将能量传播到多个跳跃（hops）之外，并混合来自语义不相关区域的信号，这可能会模糊小集群之间在异配性下尤其重要的细粒度结构差异\(He et al., 2022 (https://arxiv.org/html/2605.10975#bib.bib15)\)。此外，传统多项式基（例如 Chebyshev）受限于多项式参数化在图上的条件。在理论设定中，Chebyshev 多项式在*连续*权重函数 \(w(x)=1/\sqrt{1-x^2}\) 下的 \([-1,1]\) 区间上是正交的。尽管图滤波器将拉普拉斯谱重新缩放到 \([-1,1]\)，但真实图由于受*离散*谱测度（重新缩放后的特征值及其重数）支配，无法提供这种连续加权，导致频率通道间的泄漏以及滤波器组有效表达能力的降低\(Guo & Wei, 2023 (https://arxiv.org/html/2605.10975#bib.bib13)\)。此外，高阶多项式近似容易出错，且生成的基通常是*静态*的，不能适应局部特征/结构异配性\(Huang et al., 2024 (https://arxiv.org/html/2605.10975#bib.bib17); Zheng, 2024 (https://arxiv.org/html/2605.10975#bib.bib38)\)。另一方面，空间 GNN 通过采用邻域聚合直接滤波图信号，并且通常表现出固有的低通偏差\(Zhu & Koniusz, 2021 (https://arxiv.org/html/2605.10975#bib.bib39)\)。为了解决这个问题，最近提出的有符号消息传递方法（SMPs）结合边符号来学习节点信号之间的对比度。基于 SMP 的模型受到深度上的符号抵消影响（例如，每两层），逐渐消除异配性对比度\(Liang et al., 2024 (https://arxiv.org/html/2605.10975#bib.bib22)\)。为了防止信号符号翻转，几种空间模型采用块状消息传递（CMP）方法，按相似性将邻居分桶，然后通过全局聚合步骤整合所有块/桶\(Pei et al., 2024 (https://arxiv.org/html/2605.10975#bib.bib27)\)。这两种方法都在图区域之间混合信号。这种混合在度不平衡的图中尤为有害：密集连接的高度中心节点可以主导消息传递，侵蚀小（辐条）异配性集群的信号，导致特征无法区分（中心节点主导），并最终加剧信号过平滑\(Keriven, 2022 (https://arxiv.org/html/2605.10975#bib.bib18)\)。这些局限性促使我们设计一种滤波器，它：\(i\) 在光谱上条件良好，以防止频率通道间的泄漏；\(ii\) 具有局部性，以避免长距离污染；\(iii\) 能够学习高通和低通滤波器，且没有符号抵消的病理问题。见图 1：提出的 HMH 框架概览。该过程从输入图和节点特征开始，随后进行自适应异配性编码和层次图粗化。在每个层级，构建类感知的 Haar 基，并执行对角线光谱滤波。最后，多尺度跳跃连接融合聚合来自所有层级的信息。为了解决现有的局限性，我们提出了一种新颖的模型，称为 HMH。HMH 首先引入一个自适应异配性编码器，该编码器为同质边分配正权重，为异配边分配持久的负权重。编码器还被设计为自适应高通和低通滤波器，从而保留传统静态方法通常无法保留的高频对比度。编码器还结合结构相似性和特征亲和力，生成促进层次聚类（粗化）的每节点分数。在每个层次级别，使用该编码器构建 Haar 基，形成一个稀疏、正交的特征基，能够显式地捕捉局部低频（集群内）和高频（集群间）变化。在此基中的对角线光谱滤波选择性放大异配性通道并衰减中心节点主导的信号。采用跳跃连接的上采样技术，将每个层级过滤后的信号重新整合到原始节点中，用多尺度上下文丰富它们。粗化层次将对数地减少有效路径长度，允许梯度和信息传播，而不会因过挤压引起的指数衰减\(Di Giovanni et al., 2023 (https://arxiv.org/html/2605.10975#bib.bib7)\)。最后，我们利用层次树进行图池化以用于图分类，将池化开销从先前方法中的二次 \(O(n^2)\) 降低到近线性 \(O(n)\) 时间\(Li et al., 2024 (https://arxiv.org/html/2605.10975#bib.bib21)\)。本文的贡献在于：\(i\) 我们引入了一种无标签的自适应有符号亲和力，以防止符号抵消；\(ii\) 我们引入了第一个在近线性时间内构建正交、多尺度、稀疏光谱基的框架，能够轻松扩展到大图；\(iii\) 我们严格证明并实证确认传统 GNN 存在中心节点主导、过平滑和过挤压的问题，而我们提出的 HMH 克服了这些病理问题；\(iv\) 我们展示了 HMH 在节点和图分类任务上均达到了最先进的（SOTA）准确率，同时保持了线性扩展能力。 ## 2 相关工作 光谱滤波：早期模型，如 ChebNet\(He et al., 2021 (https://arxiv.org/html/2605.10975#bib.bib14)\)，使用截断的 Chebyshev 多项式来近似特征基。相反，通用 PageRank GNN（GPR-GNN）\(Chien et al., 2021 (https://arxiv.org/html/2605.10975#bib.bib5)\) 利用带有单项式基的通用 PageRank 权重进行近似。相比之下，BernNet\(He et al., 2021 (https://arxiv.org/html/2605.10975#bib.bib14)\) 和 JacobiConv\(Wang & Zhang, 2022 (https://arxiv.org/html/2605.10975#bib.bib33)\) 分别提供 Bernstein 和 Jacobi 多项式，以增强基的可解释性和适应性。ChebNetII\(He et al., 2022 (https://arxiv.org/html/2605.10975#bib.bib15)\) 通过采用插值解决了 Chebyshev 多项式过拟合的问题，而 OptBasisGNN\(Guo & Wei, 2023 (https://arxiv.org/html/2605.10975#bib.bib13)\) 旨在使基多项式正交以加速收敛。上述方法论继续使用密集的、固定的图范围基，从而防止全局消息混合。 层次图学习：可学习池化方法，如 DiffPool\(Ying et al., 2018 (https://arxiv.org/html/2605.10975#bib.bib37)\)、SAGPool\(Lee et al., 2019 (https://arxiv.org/html/2605.10975#bib.bib19)\)、TopKPool\(Diehl, 2019 (https://arxiv.org/html/2605.10975#bib.bib8)\)，利用节点评分在单一分辨率下粗化同质图，产生 \(O(n^2)\) 的计算成本\(Li et al., 2024 (https://arxiv.org/html/2605.10975#bib.bib21)\)。EigenPool\(Ma et al., 2019 (https://arxiv.org/html/2605.10975#bib.bib25)\) 和基于 Haar 的池化采用昂贵的特征分解来粗化图，产生 \(O(n^3)\) 的计算成本，这限制了可扩展性并忽略了局部异配性\(Wang et al., 2020 (https://arxiv.org/html/2605.10975#bib.bib32)\)。 ## 3 预备知识 令 \(G=(V,E)\) 为一个简单的无向图，其中 \(V\) 表示顶点集，\(E\) 表示边集。其邻接矩阵 \(A \in \mathbb{R}^{n \times n}\) 的条目为 \(A_{ij}=1\) 如果 \(\{i,j\} \in E\)，否则为 0，且 \(D=\mathrm{diag}(A\mathbf{1})\) 是度矩阵，其中 \(\mathbf{1}\) 是全 1 向量。给定节点特征 \(X \in \mathbb{R}^{m \times d}\) 和归一化拉普拉斯算子 \(\mathcal{L}=U\Lambda U^{\top}\)，光谱层通过 \(g(\mathcal{L})X=U\,g(\Lambda)\,U^{\top}X\) 重新缩放图傅里叶分量，其中 \(g\) 是光谱滤波器。多项式光谱方法用多项式实现 \(g\)，\(g(L) \approx \sum_{r=0}^{R}\theta_{r}\,L^{r}\)，其中 \(R \in \mathbb{N}\) 是多项式阶数。通过 \(k\) 层消息传递，GNN 通过传播算子 \(P\) 学习图信号作为多项式，这实质上诱导了传播算子 \(P\) 的全局特征基，由下式给出：
\[ H^{(k)} \approx \sum_{r=0}^{k}\Theta_{r}\,P^{r}\,X = g_{P}(P)\,X = U_{P}\,g_{P}(\Lambda_{P})\,U_{P}^{\top}X, \tag{1} \]
其中 \(U_{P}\Lambda_{P}U_{P}^{\top}\) 是 \(P\) 的特征分解，\(\Theta_{r}\) 是可学习的线性参数。 现实世界中的图通常在图的不同区域表现出不同程度的同质性。我们将*同质性*量化为 \(H_{\mathrm{lab}}=\frac{1}{\|E\|}\sum_{(u,v)\in E}[y_{u}=y_{v}]\)，其中 \(y\) 是节点标签。为了解决节点同质性之间的差异，基于符号的消息传递（SMP）\(Liang et al., 2024 (https://arxiv.org/html/2605.10975#bib.bib22); Chien et al., 2021 (https://arxiv.org/html/2605.10975#bib.bib5)\) 算法引入了有符号邻接矩阵 \(S\)，定义为 \(S_{uv}=+1\) 如果 \((u,v) \in E\) 且 \(y_{u}=y_{v}\)，\(S_{uv}=-1\) 如果 \((u,v) \in E\) 且 \(y_{u} \neq y_{v}\)。因此，每层的特征更新为：
\[ H^{(k+1)}=\sigma\!\big(S\,H^{(k)}W^{(k)}\big), \quad H^{(0)}=X, \]
其中 \(S\) 作为传播算子，\(W\) 是权重矩阵。利用公式 (1)，\(k\) 层 SMP 可以表示为 \(S\) 全局基中的光谱滤波器。为了解决 SMP 的符号翻转问题，基于块式多路聚合（CMA）的方法\(Pei et al., 2024 (https://arxiv.org/html/2605.10975#bib.bib27)\) 提议将每个节点的邻居分成 \(t\) 个通道（例如，同质/异质），并带有学习的注意力 \(\alpha_{ij,t}\)，并逐通道 \(t\) 聚合消息 \(m_{i,t}\)。 众所周知，普通的 GCN 表现出两种与深度相关的病理问题：\(i\) 过平滑，随着层数的增加，所有节点嵌入收敛到其类均值\(Epping et al., 2024 (https://arxiv.org/html/2605.10975#bib.bib10)\)；\(ii\) 过挤压\(Topping et al., 2021 (https://arxiv.org/html/2605.10975#bib.bib31)\)，当来自远距离节点的梯度（或消息）随图距离指数衰减时发生，阻止了长距离信息的流动。虽然许多异配性 GNN 旨在解决这些问题，但它们在中心节点主导图和次优基下的局限性仍然存在，如下文所述。 ## 4 现有模型的局限性 我们强调现有图学习模型中的两种故障模式，它们共同解释了在中心节点主导图上的糟糕表现\(Luan et al., 2022 (https://arxiv.org/html/2605.10975#bib.bib24); Guo & Wei, 2023 (https://arxiv.org/html/2605.10975#bib.bib13)\)。 局限性 1：中心节点主导。考虑两个小集群 \(A\) 和 \(B\) 与一个主导的中心区域 \(H^{\prime}\)（单个高度节点或高度节点的同质集群）密集连接。由于 \(H^{\prime}\) 相对于辐条（低度节点的小集群）具有显著更高的度，在消息传递期间，由此产生的更高信号贡献在统计上淹没了 \(A\) 和 \(B\) 的局部特征。尽管 \(A\) 和 \(B\) 具有不同的类标签，但这种“中心节点主导”导致嵌入漂移到一个共同的中心诱导表示，消除了它们之间的决策边界。以下定理建立了中心节点主导的理论基础，实证结果和分析将在表 3 (https://arxiv.org/html/2605.10975#S6.T3) 中呈现。 见图 2：集群 \((A, B, H^{\prime})\) 中的中心混叠现象。 ###### 定理 4.1。\(A\) 中任何节点与 \(B\) 中任何节点之间的表示距离在多层 SMP 或 CMA 之后呈指数衰减。（证明见附录 A (https://arxiv.org/html/2605.10975#A1)） 局限性 2：次优基。固定的多项式基（例如，Jacobi, Chebyshev）假设连续正交性，这在非规则图的离散谱上不成立。因此，多项式基变得相关，阻碍模型解耦频率成分并适应局部图结构的能力。 ## 5 方法论 在本节中，我们提出提出的 HMH 光谱图学习框架。HMH 执行图信号的多分辨率分析，捕捉局部相互作用和全局结构趋势，如图 1 (https://arxiv.org/html/2605.10975#S1.F1) 所示。管道以一个异配性感知的编码器开始，该编码器从局部特征和结构线索计算节点分数。这些分数指导聚类步骤，形成下一层的超节点。我们在每一层递归应用相同的编码器-聚类过程以构建完整的层次结构。在每一层，我们构建特定层的光谱基 \(U^{(\ell)}\)，使