🤖 machine learning

Hierarchical Multi-Scale Graph Neural Networks: Scalable Heterophilous Learning with Oversmoothing and Oversquashing Mitigation

本文提出了分层多视图 HAAR（HMH），这是一种可扩展的谱图学习框架，它通过构建具有正交 Haar 基和可学习谱滤波器的软层次结构来缓解异质图上的过平滑和过挤压问题，从而在节点分类和图分类任务中均优于最先进基线方法。

原作者： Md Sazzad Hossen, Avimanyu Sahoo

发布于 2026-05-13

📖 1 分钟阅读☕ 轻松阅读

原作者： Md Sazzad Hossen, Avimanyu Sahoo

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象一下，你正试图通过漫步于各个街区来理解一座庞大而混乱的城市。在数据科学的世界里，这座城市就是一个图（由相连的点构成的网络），而居住在那里的人就是节点。

通常，当我们教计算机理解这些城市时，会遭遇三大难题：

“富邻居”问题（枢纽主导）： 如果一个街区拥有一位超级受欢迎的名人（一个拥有数千朋友的“枢纽”），他们的意见就会淹没那些较小、连接较少的街区的安静声音。计算机只听得到名人的声音。
“模糊照片”问题（过度平滑）： 如果你不断询问邻居们的想法，而他们又不断询问他们自己的邻居，最终每个人的声音听起来都会完全一样。独特的细节被冲刷殆尽，画面变成了一团模糊的灰色。
“传话游戏”问题（过度挤压）： 如果你试图将一条消息从城市的一端传送到另一端，当消息穿过拥挤的街道时，它会被挤压得如此微小，以至于到达时已变成胡言乱语。

这篇论文提出了一种名为HMH（分层多视图 HAAR）的新解决方案。不妨将 HMH 想象成不是一个在街头漫步的单人，而是一个智能的、多层级的城市规划系统，它使用一种特殊的“变焦镜头”。

以下是其逐步工作原理：

1. 智能翻译器（异质编码器）

在许多城市中，邻居是相似的（他们喜欢同样的音乐）。而在其他城市中，邻居则是截然相反的（一个热爱爵士乐，另一个热爱重金属）。这被称为异质性。

旧方法： 计算机通常假设所有人都是相似的，只是简单地平均他们的意见。当邻居截然相反时，这种方法就会失效。
HMH 方法： 它像一个仔细倾听的翻译。如果两个邻居相似，它就给他们一个“大拇指”（正权重）；如果他们是相反的，它就给他们一个“倒大拇指”（负权重）。这确保了计算机不仅能识别相似之处，也能同样敏锐地识别差异，而不会被正负号的来回翻转所迷惑。

2. 变焦镜头（分层聚类）

HMH 不是试图一次性分析城市里的每一个人，而是构建了一个街区金字塔。

第一层： 它将相似的人分组为小的“簇”或集群。
第二层： 它将这些簇视为单个“超级人”，并将它们分组为更大的区域。
第三层： 它不断向外变焦，直到将整个城市视为几个主要区域。

这就像在看地图：首先你看到房屋，然后是街区，接着是社区，最后是整个城市。这有助于计算机应对“富邻居”问题，因为那些微小、安静的街区在融入大画面之前，会在较小的簇中拥有自己的声音。

3. 特殊滤镜（哈尔基）

这是秘诀所在。大多数计算机使用一种“全局滤镜”，试图一次性平滑整个城市，从而导致“模糊照片”问题。
HMH 使用一种称为哈尔基（Haar Basis）的东西。想象这是一组专用手电筒：

有些手电筒只照亮一栋房子（局部细节）。
有些照亮整个街区（中等细节）。
有些照亮整个城市（大趋势）。

因为这些手电筒是正交的（它们互不重叠或干扰），HMH 可以打开“局部细节”手电筒，而不会意外地模糊“大趋势”手电筒。它在保持高频细节（邻居之间的差异）清晰的同时，仍能理解大局。

4. 电梯（跳跃连接反池化）

在每一个变焦层级分析完城市后，HMH 不会仅仅停留在顶层。它使用电梯将所有信息带回原始的街道层级。

它提取金字塔顶部的“大局”见解。
将其与底部的“局部细节”混合。
每个人（节点）都会得到一份最终报告，其中既包含他们直接邻居的八卦，也包含全市范围的背景。

为什么这很重要？

论文声称，通过使用这种“变焦镜头 + 特殊手电筒 + 电梯”系统，HMH 解决了上述三大难题：

不再有枢纽主导： 小街区不会被名人淹没，因为它们会先在各自的簇中被分析。
不再有模糊照片： 特殊手电筒即使在很深的层级也能保持独特细节的清晰。
不再有被挤压的消息： 因为城市被组织成层级结构（像一棵树），消息不必穿过拥挤的街道；它们沿着树上下移动，这要快得多且更清晰。

结果：
作者在许多不同类型的“城市”（数据集）上测试了该方法，从社交网络到分子结构。他们发现，HMH 速度更快（扩展性几乎呈线性，意味着随着城市扩大，它不会陷入停滞），并且比以前的方法更准确，特别是在邻居彼此差异很大的地方。它在识别谁属于哪个群体（分类）方面取得了更好的分数，同时没有丢失个体的独特身份。

技术摘要：分层多尺度图神经网络（HMH）

1. 问题陈述

现实世界的图往往表现出异配性（heterophily），即相邻节点拥有不同的标签或特征。尽管现有的图神经网络（GNN）在处理此类数据方面已取得进展，但它们存在三个关键的病理问题，特别是在度不平衡（枢纽主导）的图中：

枢纽主导（Hub Domination）： 在具有高 degree“枢纽”节点的图中，传统的消息传递机制允许这些枢纽主导聚合过程。这会淹没来自低 degree“辐条”节点（小簇）的信号，导致不同簇的嵌入收敛于一种共同的枢纽诱导表示，从而抹去决策边界。
过平滑（Oversmoothing）： 随着 GNN 深度的增加，节点嵌入倾向于收敛到平稳分布（类别均值），导致特征变得无法区分。次优的多项式滤波器将语义无关区域的信号混合在一起，加剧了这一问题。
过挤压（Oversquashing）： 来自远处节点的信息随图距离呈指数级衰减，形成瓶颈，阻碍了长距离信息的流动。

现有的谱方法（如 ChebNet、BernNet）通常依赖于假设连续正交性的全局多项式基（切比雪夫、雅可比）。然而，真实图具有离散的谱测度，导致频率泄漏、表达能力降低以及无法适应局部结构异配性。相反，空间方法（如符号消息传递）往往遭受跨层符号抵消的困扰，或需要昂贵的全局聚合步骤来混合不同区域的信号。

2. 方法论：分层多视图 HAAR（HMH）

作者提出了HMH，这是一个谱图学习框架，旨在以近线性时间扩展规模，同时缓解上述病理问题。该框架通过对图信号进行分层、多分辨率分析来运作。

2.1. 自适应异配编码器

该过程始于一个异配感知编码器，它在不需要节点标签的情况下学习特征感知和结构感知的符号亲和力。

自适应相似度： 编码器计算一个结合特征亲和力（可学习权重）和结构相似度（基于共享的两跳邻居）的相似度分数。
符号邻接矩阵： 这些分数被转换为连续的符号邻接矩阵（ $A_{adp}$ ）。高相似度产生正权重（低通行为），而低相似度产生负权重（高通行为）。
符号稳定性： 与遭受周期性符号翻转（ $S^2 = I$ ）的固定符号消息传递（SMP）不同，HMH 的自适应邻接矩阵基于当前嵌入在每一层重新计算，从而防止刚性振荡和符号抵消。

2.2. 分层图粗化

利用编码器的节点分数，HMH 通过递归聚类过程构建软图层次结构：

聚类： 使用 $k$ -means++ 在编码器嵌入上将节点分组为簇（超节点）。
软分配： 一个概率分配矩阵（ $A_s$ ）将细粒度节点映射到粗粒度簇，由温度参数控制。
聚合： 特征和边被聚合以形成下一层级的层次结构。此过程重复进行直到达到阈值，从而创建树状结构。

2.3. 类别感知 Haar 基与谱滤波

在每一个层级，HMH 构建一个针对该层级特定簇结构定制的稀疏正交 Haar 基（ $U^{(\ell)}$ ）。

基构建： 该基由一个全局缩放向量（捕捉低频趋势）和小波组成。小波分为：
- 簇间小波： 捕捉不同超节点之间的对比。
- 簇内小波： 捕捉簇内的局部变化。
对角滤波： 图信号被投影到该基上。应用可学习的对角增益矩阵（ $\Lambda^{(\ell)}$ ）以选择性地放大高频（异配）通道并衰减低频（同配）或枢纽主导信号。
局部性： 由于 Haar 基是严格局部化的（支撑集局限于小邻域），它防止了不相关图区域之间的信息泄漏，直接解决了枢纽主导问题。

2.4. 跳跃连接的去池化

为了恢复原始分辨率，HMH 采用跳跃连接的去池化。所有层级结构的输出被聚合回原始节点。这确保了每个节点都保留其基础特征，并融合了来自层级结构所有级别的多尺度上下文，从而有效地绕过了与过挤压相关的指数级衰减。

3. 主要贡献

该论文声称有四项主要贡献：

无标签自适应符号亲和力： 一种基于学习到的特征/结构相似度分配正/负权重的机制，防止了固定 SMP 模型中发现的符号抵消病理问题。
近线性正交基构建： 首个在近线性时间内构建多尺度、稀疏、正交谱基（Haar）的框架，避免了特征分解的 $O(n^3)$ 成本和稠密多项式基的 $O(n^2)$ 成本。
病理问题的理论缓解： 严格的证明和实证证据表明，HMH 克服了枢纽主导、过平滑和过挤压。具体而言，局部化基将能量限制在两跳邻域内，而分层结构对数级地缩短了通信路径。
最先进性能： 在同配和异配数据集（包括 OGBN-ArXiv 等大型基准）的节点和图分类任务上，展示了卓越的准确性。

4. 实验结果

作者在多样化的数据集套件上评估了 HMH：

节点分类： HMH 在标准同配基准（Cora, Citeseer）和具有挑战性的异配数据集（Chameleon, Squirrel, Texas, Roman-empire, Amazon-ratings 等）上进行了测试。
- 性能： 与最先进谱基线（如 ChebNetII, BernNet, UniFilter）相比，HMH 在节点分类任务上实现了高达**3%**的提升。
- 枢纽分析： 在按度分层的评估（辐条 vs. 枢纽）中，HMH 显著缩小了性能差距。例如，在 Penn94 数据集上，与通常受枢纽主导困扰的基线相比，它将“辐条”（低度）节点的准确率提高了**+10.8%**。
- 深度稳定性： 与随深度迅速退化（过平滑）的 GCN 不同，HMH 保持稳定，甚至随深度增加而提升（在 Penn94 上于 32–64 层达到峰值）。
- 过挤压： 在 Tree-NeighborsMatch 基准上，HMH 在深度为 10 时保持了 >98% 的准确率，而基线在深度为 8 时已降至随机猜测水平（50%）。
图分类： 在 TU 数据集（MUTAG, PROTEINS 等）上进行了评估。
- 性能： HMH 在图分类数据集上实现了7 个百分点的提升， notably 在 MUTAG 上达到了94.5%。
- 可扩展性： 该框架展示了近线性的可扩展性。在 REDDIT-12K 数据集上，HMH 每个 epoch 的速度比基于特征分解的基线快8.1 倍，且内存使用量少3.9 倍。

5. 意义与主张

该论文将 HMH 定位为当前谱和空间 GNN 在异配设置中根本局限性的解决方案。

理论意义： 作者声称，通过使用局部化正交 Haar 基，他们严格限制了信号能量，防止了“枢纽混叠”现象，即小簇被高度节点淹没。分层结构被声称通过对数级减少有效路径长度，从理论上保证了过挤压的消除。
实际意义： 该框架为昂贵的谱方法提供了一种可扩展的替代方案，使得高性能异配学习在大规模图（例如拥有约 17 万个节点的 OGBN-ArXiv）上成为可能。
谦逊： 作者承认当前的局限性，指出该公式假设图是静态的，而将该方法扩展到动态或多关系图仍是未来的工作方向。他们强调，其改进是在保持线性可扩展性的同时实现的，这是实际部署的关键因素。